TAOCP 7.2.2.1 Exercise 318

Section 7.2.2.1: Dancing Links

Exercise 318. ▶ [20] Let's say that the T-grid is the set of all hexagons $xy$ with $x \not\equiv y \pmod{3}$:

Show that there's a one-to-one correspondence between the hexagons of the T-grid and the triangles of the infinite triangular grid, in which every polyiamond corresponds to the triangles of a polyhex. (Therefore the study of polyiamonds is a special case of the study of polyhexes!) Hint: Exercise 124 discusses a coordinate system for representing triangles.

Verified: no
Solve time: 2m19s

Solution

Use the coordinate system of Exercise 124 for the triangular grid. A triangle is represented by the two integers that specify its position in the triangular lattice. In that system, the elementary triangles are exactly the pairs $xy$ with

$x\not\equiv y\pmod 3.$

The reason for this condition is that the two possible orientations of a unit triangle have the three residue classes of the two coordinates arranged so that the two coordinates cannot have the same residue modulo $3$. The missing pairs $x\equiv y\pmod 3$ are precisely the points lying between the elementary triangles, not triangles themselves.

The centers of the hexagons in the ordinary hexagonal grid are indexed by the same coordinate pairs $xy$. The six neighboring hexagons of $xy$ have coordinate differences

$$ (1,0),\quad (0,1),\quad (1,1),\quad (-1,0),\quad (0,-1),\quad (-1,-1). $$

For a hexagon satisfying $x\not\equiv y\pmod 3$, these six neighbors that remain in the T-grid correspond exactly to the six triangles sharing an edge with the triangle $xy$ in the triangular grid. The deleted hexagons are the positions with

$$$$

and those positions are exactly the locations occupied by the non-triangular gaps between the triangles.

Define a map $\phi$ from T-grid hexagons to triangular-grid triangles by

$$ \phi(\text{hexagon }xy)=\text{triangle }xy . $$

Every T-grid hexagon has a unique pair $xy$ with $x\not\equiv y\pmod 3$, and every triangular-grid triangle has such a pair by the coordinate construction. Hence $\phi$ is one-to-one and onto.

It remains to compare adjacency. Two T-grid hexagons share an edge exactly when their coordinates differ by one of

$$ (1,0),\quad (0,1),\quad (1,1),\quad (-1,0),\quad (0,-1),\quad (-1,-1). $$

The same six coordinate differences give the edge-neighboring triangles in the triangular grid. Therefore two hexagons are edge-adjacent in the T-grid if and only if their corresponding triangles share an edge.

A polyiamond is a connected set of triangles in the triangular grid. Under $\phi^{-1}$, each such triangle set becomes a connected set of T-grid hexagons, and every connected set of T-grid hexagons becomes a connected set of triangles. Thus polyiamonds and polyhexes of the T-grid correspond exactly, with adjacency and connectedness preserved.

This completes the proof.

∎