TAOCP 7.2.2.1 Exercise 276

Exercise 276. [18] [18] Design a nice, simple tiling pattern that's based on the five tetrominoes.

Verified: no
Solve time: 3m35s

Solution

Let the five tetrominoes be denoted by $I$ (straight), $O$ (square), $T$, $L$, and $S$ (skew). Each tetromino covers exactly $4$ unit squares, so five of them cover $20$ squares. A natural host region is therefore a $4\times 5$ rectangle.

A periodic tiling of the plane is obtained once a single $4\times 5$ block is tiled by the five tetrominoes exactly once each, since translations of that block by vectors $(4,0)$ and $(0,5)$ then cover the plane without gaps or overlaps.

Consider the $4\times 5$ grid with coordinates $(r,c)$ where $0\le r\le 3$ and $0\le c\le 4$. The tiling is given by the following disjoint placement of tetrominoes.

The $O$ tetromino occupies the $2\times 2$ square in the upper-left corner:

$$ O={(0,0),(0,1),(1,0),(1,1)}. $$

The $I$ tetromino is placed vertically in column $4$:

$$ I={(0,4),(1,4),(2,4),(3,4)}. $$

The $T$ tetromino is placed with its $3$-cell bar in row $2$ and its stem upward:

$$ T={(2,1),(2,2),(2,3),(1,2)}. $$

The $L$ tetromino occupies the lower-left $L$-shape:

$$ L={(3,0),(3,1),(2,0),(3,2)}. $$

The $S$ tetromino occupies the remaining four cells in a skew configuration:

$$ S={(1,3),(2,3),(2,2),(3,3)}. $$

Each set consists of four distinct grid squares, and direct inspection shows that all five sets are pairwise disjoint. The union of the $O$ and $I$ placements occupies $8$ squares, leaving $12$ squares. The placements of $T$, $L$, and $S$ occupy exactly those remaining squares, since

$$ |T|+|L|+|S|=12 $$

and every remaining coordinate in the $4\times 5$ grid lies in exactly one of these three sets.

Each shape matches a valid tetromino geometry: $O$ is a $2\times 2$ block, $I$ is a $4$-cell segment, $T$ has a $3$-cell bar with one attached cell, $L$ is a $3$-cell arm with one extension, and $S$ is a two-by-two skew adjacency.

Thus the $4\times 5$ rectangle is tiled exactly once by the five tetrominoes, and repeating this block by translation yields a periodic tiling pattern of the plane. This completes the construction. ∎