TAOCP 2.3.4.3 Exercise 2

Exercise 2. [**] [20] Show that if rotation of tetrad types is allowed, it is always possible to tile the plane.

Verified: yes
Solve time: 15m54s

Let $t$ be any tetrad type in the given nonempty set of tetrad types. Write its side labels, in clockwise order, as

$$ (N,E,S,W)=(a,b,c,d). $$

Since rotations are allowed, we may place copies of $t$ in any of its four orientations.

The idea is to use only the tetrad $t$, arranging its orientations in a checkerboard pattern.

For a tile in orientation $r\in{0,1,2,3}$, where $r$ denotes a rotation by $90r^\circ$, the label appearing on a side is obtained by cyclically shifting the labels. In particular:

the east side of orientation $r$ carries the label originally on side $1-r\pmod 4$;
the west side of orientation $s$ carries the label originally on side $3-s\pmod 4$.

Suppose two horizontally adjacent tiles have orientations $r$ and $s$. Their common edge matches whenever

$$ 1-r \equiv 3-s \pmod 4, $$

that is,

$$ s \equiv r+2 \pmod 4. $$

Similarly, for two vertically adjacent tiles, the south side of orientation $r$ and the north side of orientation $s$ match whenever

$$ 2-r \equiv 0-s \pmod 4, $$

which again gives

$$ s \equiv r+2 \pmod 4. $$

Therefore every adjacency is automatically satisfied if neighboring tiles always differ by a rotation of $180^\circ$.

Now tile the plane as follows:

$$ \text{orientation at }(m,n)= \begin{cases} 0, & m+n \text{ even},\[4pt] 2, & m+n \text{ odd}. \end{cases} $$

This is a checkerboard pattern of copies of $t$, alternating between orientation $0^\circ$ and orientation $180^\circ$.

Every horizontal or vertical neighbor differs by $2\pmod 4$, so the calculation above shows that the labels on their common edge are identical. Hence all matching conditions are satisfied.

Thus the entire plane is tiled using copies of the single tetrad type $t$, with alternating $0^\circ$ and $180^\circ$ rotations.

$$ \boxed{\text{If rotations of tetrad types are allowed, every nonempty set of tetrads can tile the plane.}} $$