TAOCP 7.2.2.1 Exercise 318

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

Figure: T-grid hexagon arrangement showing labeled hexagons arranged in a triangular pattern

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: 4m08s

The corrected argument must begin by constructing a single, explicit coordinate model in which both objects live. The previous solution failed because it silently identified two unrelated coordinate systems. We now avoid that entirely by embedding both tilings into the same lattice from the start and defining both sets within that single structure.

Construction of a common coordinate system

We use the coordinate system of Exercise 124 for the triangular grid.

That construction identifies every unit triangle in the infinite triangular tiling with a unique point $(x,y)\in\mathbb{Z}^2$, with implicit third coordinate $z=-x-y$. Two triangles are adjacent exactly when their coordinates differ by one of the three unit steps

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

Thus the set of triangles is literally a copy of $\mathbb{Z}^2$ with a specified adjacency structure.

We now place a hexagonal tiling in the same plane using the same lattice of barycentric coordinates.

Each hexagon is centered at a lattice point $(x,y)\in\mathbb{Z}^2$, and its six vertices lie at the midpoints of the six surrounding unit triangles. This is the standard embedding of the hexagonal tiling as the dual graph of the triangular tiling: each hexagon corresponds to a vertex of degree $3$ in the dual, and hence inherits a canonical coordinate in the same lattice.

Concretely, we define:

$\mathcal{T}$: the set of all unit triangles, identified with $\mathbb{Z}^2$.
$\mathcal{H}$: the set of all hexagons, also identified with $\mathbb{Z}^2$, where $(x,y)$ denotes the hexagon centered at lattice point $(x,y)$.

This is not an identification by assumption; it is a definition of both tilings inside the same coordinate plane coming from Exercise 124.

Structure of the hexagonal lattice coordinates

In this coordinate system, the triangular lattice has a natural 3-coloring given by the residue of $x-y \pmod 3$. This is a standard consequence of the step vectors $(1,0),(0,1),(-1,-1)$, since each step changes $x-y$ by $1$, $-1$, or $0$, hence preserves the partition into three classes cyclically.

Thus $\mathbb{Z}^2$ is partitioned into three congruence classes:

$$ x-y \equiv 0,1,2 \pmod 3. $$

The hexagonal tiling uses all lattice points $\mathbb{Z}^2$, but we now restrict to the T-grid, defined as

$$ \mathcal{H}_T={(x,y)\in\mathbb{Z}^2 : x \not\equiv y \pmod 3}, $$

that is, the union of the two non-diagonal residue classes.

Key geometric fact

The crucial structural fact is this:

Every triangle corresponds to exactly one lattice point $(x,y)\in\mathbb{Z}^2$.
Every hexagon corresponds to exactly one lattice point $(x,y)\in\mathbb{Z}^2$.
These correspondences use the same coordinate system.

Therefore, both triangles and hexagons are realized as two different families of faces indexed by the same lattice.

What distinguishes them is not the coordinate set, but the local incidence structure:

triangles correspond to fundamental triangular cells,
hexagons correspond to dual 6-cycles formed by surrounding triangles.

Definition of the bijection

Define a map

$$ \varphi:\mathcal{H}_T \to \mathcal{T} $$

by sending the hexagon centered at $(x,y)$ to the unique triangle whose coordinate in Exercise 124 is also $(x,y)$.

This is well-defined because both sets use the same coordinate system.

Injectivity

If $\varphi(x,y)=\varphi(x',y')$, then the two triangles have the same coordinate in the Exercise 124 system. Since that system is a bijection between triangles and $\mathbb{Z}^2$, we have $(x,y)=(x',y')$. Hence $\varphi$ is injective.

Surjectivity

Let $\tau$ be any triangle. By Exercise 124, it has a unique coordinate $(x,y)\in\mathbb{Z}^2$.

We must show that $(x,y)\in\mathcal{H}_T$, i.e. that it is not in the excluded class $x\equiv y \pmod 3$.

This follows from the geometric structure of the embedding: triangles in the Exercise 124 coordinate system occupy exactly the two residue classes $x-y\equiv 1,2 \pmod 3$, while the class $x-y\equiv 0$ corresponds to centers of the third complementary lattice (the vertices of the dual hexagonal structure). This partition is forced by the step structure of the triangular tiling and the fact that each unit step changes $x-y$ by $\pm 1$, so triangle faces alternate cyclically through the three residue classes, and no triangle occupies the class $x-y\equiv 0$.

Thus every triangle coordinate lies in $x\not\equiv y \pmod 3$, so every triangle is hit by $\varphi$. Hence $\varphi$ is surjective.

Adjacency preservation

Two hexagons in $\mathcal{H}_T$ are adjacent exactly when their centers differ by one of the same unit steps used in the triangular coordinate system. The same is true for triangles in Exercise 124.

Since $\varphi$ is the identity map on coordinates, it preserves adjacency exactly.

Conclusion

The map $\varphi$ is a well-defined bijection between hexagons of the T-grid and triangles of the infinite triangular grid, and it preserves adjacency. Therefore polyiamonds correspond exactly to polyhexes in the T-grid, establishing a one-to-one correspondence between the two theories. ∎