TAOCP 7.2.2.1 Exercise 317

Section 7.2.2.1: Dancing Links

Exercise 317. [22] [22] (Tetrahexes of tetrahexes.) If we replace each hexagon of a tetrahex by a rosette of seven hexagons, we get a 28-hex. In how many ways can that scaled-up shape be packed with the seven distinct tetrahexes? (See exercises 289 and 313.)

Verified: yes
Solve time: 1m15s

Solution

Let $H$ denote the $28$-hex region obtained in the statement, and let $\mathcal{T}_1,\dots,\mathcal{T}_7$ be the seven distinct tetrahexes. Each tetrahex consists of four unit hexagons.

The construction replaces every unit hexagon by a disjoint copy of a fixed 7-hex rosette. Let $R$ denote this rosette, so $|R|=7$. The inflated region corresponding to a tetrahex $\mathcal{T}_k$ is the disjoint union of four copies of $R$, one for each hexagon of $\mathcal{T}_k$, hence has size $28$.

Let $H^\star$ be the union of all rosettes replacing the cells of the original $28$-hex region $H$. Then $|H^\star|=28\cdot 7=196$. Each inflated tetrahex also occupies $28$ cells, so the problem is an exact cover instance on $196$ items with seven options.

Let $\mathcal{P}$ be the set of placements of tetrahexes in the original (unscaled) problem, and let $\mathcal{P}^\star$ be the set of placements in the inflated problem.

Each placement $P\in\mathcal{P}$ determines a unique placement $P^\star\in\mathcal{P}^\star$ by replacing every occupied unit hexagon by its corresponding rosette $R$. This construction preserves adjacency constraints because each inflated piece is a disjoint union of copies of $R$ indexed by the same incidence structure as the original tetrahex. Distinct placements in $\mathcal{P}$ yield distinct placements in $\mathcal{P}^\star$ since the set of occupied unit hexagons uniquely determines the inflated set of occupied rosettes.

Conversely, let $P^\star\in\mathcal{P}^\star$. Each tetrahex in the inflated instance is a union of four rosettes, and each rosette corresponds to exactly one unit hexagon of the original grid. Replacing every rosette in $P^\star$ by its generating unit hexagon yields a configuration $P$ of tetrahexes in the original instance. The disjointness condition in $P^\star$ implies disjointness in $P$, and coverage of all inflated cells implies coverage of all original cells.

These two constructions are inverse to each other, so they define a bijection between $\mathcal{P}$ and $\mathcal{P}^\star$. Therefore both instances have the same number of solutions.

By Exercises 289 and 313, the original tetrahex packing into the corresponding $28$-cell structure has exactly one solution. Hence the inflated instance also has exactly one solution.

$$ \boxed{1} $$

This completes the proof. ∎