Dang! No solutions were received for last week’s problem; a couple of people made a decent start but didn’t send in a complete solution before time was up. So, alas, we’ll just have to post our own solution this time!
Of course we welcome comments as always. I actually found this problem in an old American Mathematical Monthly (February 1998, problem 10641, proposed by Jerrold R. Griggs), where the problem editors certainly give much more than a week’s worth of time to submit solutions! But this one I managed to solve it after mulling it over for a couple of days, so I thought it would be quite manageable (although not quite trivial; more on this below). Plus, I thought it was a cute little problem. Oh well.
Solution by Todd and Vishal: An rectangle is tileable by triominoes (“L-shaped” unions of 3 of the 4 unit squares in a rectangle) if and only if three conditions hold:
- Both ;
- ;
- Whenever is odd, we also have .
Proof: (Necessity) The condition is clear since each tile has two rows and two columns, and the condition is clear since the rectangle has squares and each tile consists of squares.
Lemma 1: For , if the rectangle is tileable, then the rectangle is tileable.
Proof: Given a tiling of the rectangle, consider the tiles placed along an edge of length . By inspection, the tile containing the middle square along that edge must contain one of the corners along that edge, and must not contain the non-corner square adjacent to the middle square. So there is only one way to cover that middle and corner with a tile. This in turn fixes the placement of the tile containing the other corner along that edge, and the two tiles together form a rectangle. Removing that rectangle, we see the rest of the triominoes tile the rectangle that remains. .
This lemma shows that no tiling exists for a rectangle if is odd; otherwise we could tile the rectangle. So the third condition is also necessary.
Now we prove sufficiency. First consider the case where is even. One of is even (say ), and also either or . Say , so that and ; then it is clear that we can tile the rectangle with rectangles, each tiled by two triominoes. If on the other hand ( and) , say , then either is even (and a tiling exists by the case we just considered, switching the roles of and ); or, is odd. In that case, ; we have already proven that the rectangle can be tiled, and also that the rectangle can be tiled, and then we just put these two tilings together to tile the rectangle.
Now consider the case where is odd. Here we assume that both and . So both are at least , and if (say) , then is at least .
Lemma 2: The rectangle can be tiled by triominoes.
Proof:
Corollary: Any rectangle can be tiled, if are nonnegative integers. (This completes the proof of sufficiency.)
Proof: It suffices to tile a rectangle and a rectangle. The second case we’ve already treated. For the first case, simply put together tilings of the rectangle and the rectangle (which we have already treated). We are done.
Remarks: The case where is even is relatively “easy”; I expect most people thinking about this problem got that far in the analysis. The case where is odd is harder; one has to observe the crucial lemma 2 or something like it. In my own case, I at first thought maybe there weren’t any solutions in the odd case (and I think the people who submitted a partial solution may have thought the same), first because it’s not at all obvious, and second because lemma 1 already rules out the case (so that one may be tempted to extrapolate from there).
Here, something very typical happened: after failing to find an obvious proof of impossibility for the odd case, I tried to get at this alleged impossibility by pushing in the opposite direction: seeking a way to construct such a tiling and feeling for obstructions. [It’s that funny kind of dialectic one sometimes experiences in mathematical problem-solving, very reminiscent of Lakatos’s Proofs and Refutations.] It wasn’t long before I bumped up against a tiling after all, and at that point thought a should also be possible, which I then got after a few minutes. Then it was just a matter of mopping up.
For tiling problems in general, there’s another approach which one could try to establish the impossibility of tiling a region, if one is good at combinatorial group theory. The idea is that a tile like a triomino defines a word (up to conjugacy) in the free group on two generators : you just read off the word by following along the perimeter. For example, for a triomino in the “L” position (remove the northeast corner in a square), if you start at the southwest corner and move counterclockwise around the triomino, you read off the directions where “one unit right” and “one unit up”. (Starting at other positions, one gets a conjugate of that word.) Similarly one gets words for the triominoes in the other three positions, and the relator subgroup for our tiling problem is the smallest normal subgroup containing these words.
The observation is this: if a planar region interior to a simple closed rectangular curve is tileable, then the curve describes a word belonging to the relator subgroup. For example, the word for a rectangle might be , and from one of the tilings of the rectangle we can read off
where the words in parentheses are (conjugate to) words for triominoes. By the same token, if the word corresponding to a curve is not in the relator subgroup (is not the identity in the quotient group defined by the presentation), then the region is not tileable. For example, one can imagine a proof that certain tilings are impossible, by exhibiting a suitable representation of the group being presented.
4 comments
Comments feed for this article
July 4, 2008 at 5:50 am
Nilay
Todd
I only tried out 3X3 and 3X5 rectangles which can not be tiled while trying to figure out if the odd case can be tiled.
July 4, 2008 at 11:53 am
Todd Trimble
Yeah, I went through a similar process. In retrospect, one is stymied in the “3 x odd” case because there’s just not much room for maneuver in one of the directions.
July 7, 2008 at 8:46 pm
Nilay Vaish
Todd, have you tried solving this?
http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/Challenges/July2008.html
July 7, 2008 at 10:16 pm
Todd Trimble
I hadn’t seen it before, no. For the first problem, I so far don’t see a way of getting more than 4 distinct pentominoes covered by a single hexamino, and I’m not seeing a way to cover all 12 pentaminoes with a polyomino with less than nine squares.
I haven’t written out detailed formal proofs that my particular polyominoes are optimal, although I have a sense of how such proofs would go. At the same time, I’d be delighted if someone proved me wrong! Did you do this problem yourself, Nilay?