9
$\begingroup$

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?

  • 0
    (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!)2011-10-06

1 Answers 1

8

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)$.

  • 0
    _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?2011-10-06
  • 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.2011-10-06
  • 0
    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?2011-10-07
  • 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.2011-10-07
  • 0
    Thank you very much :) So, just to make sure I got it right, the only possibilites are 3a x 4b and 12 x n for n>=6, right? I din't overlook anything in your solution?2011-10-07
  • 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.2011-10-07