Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

OK, so I stumbled upon a problem. Namely, in what ways can I arrange (using any number of pieces) pieces like this:

F-polyomino

in such a way to form a rectangle? We can flip and rotate the pieces but not cut them in any manner.

I know I can create a $3 \times 4$ rectangles:

two F-polyominos

using two of these blocks. It implies we can also create any $3a \times 4b$ rectangle (for positive integers $a$ and $b$) But what else? Doesn't seem there's anything... I can't prove there isn't, though. Could you help me?

share|improve this question
    
(I changed the title to something a little closer to what I think the problem's intent is; @Batarang, if you think I'm wrong then please change it back!) –  Steven Stadnicki Oct 6 '11 at 17:24
add comment

1 Answer

up vote 7 down vote accepted

In fact, there's a simple coloring proof that every rectangle tiled by this hexomino has one side divisible by $4$; consider a $(4m+2)\times(4n+2)$ rectangle and color the cells with both coordinates even black, all other coordinates white. Each F hexomino covers an even number of black cells no matter its placement (since it consists of a single shape copied with a two-cell displacement), but the $(4m+2)\times(4n+2)$ rectangle has an odd number of black cells, so it can't be tiled. (And of course, if a $(4m+2)\times\mathrm{odd}$ rectangle were tileable, then it could just be doubled up into a $(4m+2)\times(4n+2)$ rectangle).

On the other hand, the rectangles of size $3a\times 4b$ don't exhaust all the possible tilings, because with the $3\times 4$ rectangle as building block you can craft other shapes - for instance, a $12\times 7$ rectangle can be done by vertically stacking four 'horizontal' boxes next to three 'vertical' boxes also stacked vertically, and this along with the trivial $12\times 6$ and $12\times 8$ tilings means that $12\times n$ rectangles are possible for all $n\geq 6$. This leaves only the $12\times 5$ rectangle (which obviously can't be tiled by $3\times 4$ rectangles), and unfortunately I don't have an answer for that one; the page at http://www.math.ucf.edu/~reid/Polyomino/f6_rect.html (from which I shamelessly stole the proof above) suggests that the $3\times 4$ is the only 'prime' rectangle tiling, but gives no proof beyond that one side must be divisible by $4$.

Addendum: After some playing around it turns out to be relatively straightforward to show that the $12\times 5$ rectangle is impossible. Consider the top ($5$-wide) edge, and the pieces that make it up; since the extremal pieces of the F are either $1$, $2$, or $4$ cells wide, then this has to be either $4+1$, $2+2+1$ or $2+1+1+1$. The latter is easy to rule out, since at least one of the $1$-cell Fs will extend beyond the bounds of the box; similarly, in a $2+2+1$ configuration, one of the $2$-cell Fs will either leave unfillable holes against the outside wall of the box or unfillable holes in the interior. Finally, for the $4+1$ configuration it's easy to see that there's only one legal configuration of these pieces that covers that edge without going past the bounds of the box: an F covering $(0,0)$, $(0,1)$, $(1,1)$, $(0, 2)$, $(0, 3)$, and $(1,3)$ and an F covering $(1,0)$, $(2,0)$, $(2,1)$, $(3,0)$, $(4,0)$ and $(4,1)$. Now consider the cell at $(3,1)$; this cell can't be covered by an F laid 'horizontally' (any such would either extend past the bounds of the box or overlaps the cell at $(1,1)$), and filling it with a vertical F leaves an unfillable hole either at $(1,2)$ or $(4,3)$.

share|improve this answer
    
for instance, a 12×7 rectangle can be done by stacking four boxes 'horizontally' next to three boxes 'vertically' - erm.. can it? Stacking as you say leaves us with 4*4+3*2=22 on the edge, doesn't it? –  Batarang Oct 6 '11 at 18:08
1  
Batarang: Sorry, description failure on my part. :-) Imagine stacking 4 'horizontal' boxes vertically on top of each other to form a 12(height)x4(width) rectangle; now stack 3 'vertical' boxes vertically on top of each other to form a 12(height)x3(width) rectangle. Place those two rectangles next to each other to get a 12x7. –  Steven Stadnicki Oct 6 '11 at 18:28
    
Thank you! I don't get one thing, though. Why does showing that we can't tile (4m+2)×(4n+2) imply that one side has to be divisible by 4? I mean, there are also possibilites of (4m+3)x(4m+3), (4m+1)x(4m+1), (4m+1)x(4m+3) and so on. Do we need to prove their unability to being tiled too? –  Batarang Oct 7 '11 at 13:41
1  
@Batarang: Those all come almost 'for free' - the F has an even number of cells, so any tiling of it into a rectangle has to have at least one edge even; otherwise the total area of the rectangle is odd, and no even number can divide into an odd number. Alternately, you can actually use the fact that there's no (4m+2)x(4n+2); by quadrupling up on any of the 'missing' possibilities you offer you would get a (4r+2)x(4s+2) rectangle for some r and s (since doubling any odd number gives a number of form 4n+2), and so the impossibility proof for that case carries over. –  Steven Stadnicki Oct 7 '11 at 15:09
1  
@batarang That's correct; those are the only possibilities that fit the constraints. The proof shows that one edge must be a multiple of 4; and since the F-hexomino has an area of 6, any rectangle it tiles must have an area divisible by 3, so at least one side length must be a multiple of 3. Either the side that's a multiple of 3 and the side that's a multiple of 4 are the same (the 12 x n case) or they're different (the 3a x 4b case). Note that 12 x 3 and 12 x 4 are possible too, but of course they fall into the 3a x 4b case. –  Steven Stadnicki Oct 7 '11 at 17:15
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.