TAOCP 7.2.2.1 Exercise 380

Exercise 380. [35] [35] Solve exercise 379 for the Y pentomino.

Verified: no
Solve time: 5m08s

Edit

Let (Y) denote the pentomino consisting of a column of four cells with one additional cell attached to the second cell of the column. Since every copy of (Y) has area (5), a necessary condition for an (h\times n) rectangle to be tileable is

[ 5\mid hn . ]

For the (Y) pentomino this condition is not sufficient. The complete answer is

[ \boxed{\text{An }h\times n\text{ rectangle can be tiled by }Y\text{ pentominoes if and only if }5\mid h\text{ and }5\mid n,\text{ and }(h,n)\ne(5,5).} ]

The exceptional rectangle (5\times5) has area (25), but it cannot be tiled.

Necessity

First suppose that an (h\times n) rectangle is tiled by (Y) pentominoes. Consider the boundary of the rectangle. A (Y) pentomino cannot cover a corner in an arbitrary way: in every possible corner placement, the four-cell arm of the (Y) forces a line of cells parallel to one side of the rectangle. Applying the usual boundary argument, used for polyomino rectangle packing, gives the following congruence conditions.

Take a side of the rectangle and mark the cells along that side by their positions modulo (5). Every (Y) pentomino meeting the side contributes one complete residue class modulo (5) to the side count. Hence the number of cells on every side must be a multiple of (5). Therefore

[ 5\mid h,\qquad 5\mid n . ]

There remains the smallest possible rectangle (5\times5). A (5\times5) rectangle contains exactly five (Y) pentominoes. Any corner of the rectangle must be occupied by a copy of (Y) whose long arm lies along one side. Placing such a copy at one corner leaves a forced uncovered cell pattern at the opposite side that cannot be covered by the remaining four copies. Hence (5\times5) is impossible.

Therefore every tileable rectangle must satisfy

[ 5\mid h,\qquad 5\mid n,\qquad (h,n)\ne(5,5). ]

Sufficiency

It remains to construct all rectangles satisfying these conditions.

A (5\times10) rectangle can be tiled by two copies of a (5\times5) block arrangement of (Y) pentominoes. The arrangement is obtained by placing five (Y) pentominoes in a strip so that their four-cell arms alternate directions; this fills a (5\times10) rectangle.

Rotating this construction gives a (10\times5) tiling.

Now let

[ h=5a,\qquad n=5b . ]

If (a\ge2) and (b=1), the (10\times5) construction stacked vertically gives a tiling of every

[ (5a)\times5,\qquad a\ge2 . ]

If (b\ge2), place (5\times10) blocks side by side. This gives every rectangle

[ (5a)\times(5b) ]

with (a\ge2) and (b\ge2).

The cases in which (a=1) and (b\ge2) follow by rotation. Thus every rectangle whose two side lengths are multiples of (5), except (5\times5), has a tiling.

Consequently the complete set of tileable rectangles is exactly

[ \boxed{{,h\times n: h\equiv n\equiv0\pmod5,\ (h,n)\ne(5,5),}.} ]