TAOCP 2.3.4.3 Exercise 3
**Answer:** No.
Exercise 3. [**] [M23] If it is possible to tile the upper right quadrant of the plane when given an infinite set of tetrad types, is it always possible to tile the whole plane?
Verified: yes
Solve time: 2m43s
Answer: No.
A valid counterexample can be constructed with an infinite set of tetrad types.
For each pair of integers $i,j\ge 0$, define a tetrad type $T_{i,j}$. Label its edges as follows:
- west edge: $i$,
- east edge: $i+1$,
- south edge: $j$,
- north edge: $j+1$.
Two adjacent tetrads may be placed next to each other only when the labels on their common edge agree.
Consider the upper right quadrant, whose unit squares are indexed by coordinates $(i,j)$ with $i,j\ge0$. Place $T_{i,j}$ in square $(i,j)$.
Horizontal adjacencies match because
$$ \text{east}(T_{i,j})=i+1=\text{west}(T_{i+1,j}), $$
and vertical adjacencies match because
$$ \text{north}(T_{i,j})=j+1=\text{south}(T_{i,j+1}). $$
Hence the upper right quadrant is tiled.
Now suppose, for contradiction, that the whole plane could be tiled.
Let some tile $T_{i,j}$ occur in the tiling. If a tile $T_{a,b}$ lies immediately to its west, then matching of the common edge gives
$$ a+1=i, $$
so $a=i-1$. Thus every step one square to the west decreases the first index by $1$.
After $k$ consecutive steps to the west, the first index must therefore be $i-k$.
Since the plane extends arbitrarily far to the west, we may choose $k=i+1$. Then a tile with first index
$$ i-(i+1)=-1 $$
would be required. But no tetrad type $T_{r,s}$ is defined for $r<0$.
This contradiction shows that no tiling of the whole plane exists.
Therefore there is an infinite set of tetrad types that tiles the upper right quadrant but does not tile the whole plane. Hence the statement is false.
$$ \boxed{\text{No, a tiling of the upper right quadrant does not necessarily extend to a tiling of the whole plane.}} $$