TAOCP 7.2.2.1 Exercise 310
The lower bound is correct and cannot be improved: since each hexiamond has area $6$, the 12 pieces cover $72$ unit triangles, and any $7 \times m$ strip must satisfy 7m \ge 72 \;\;\Rightarrow\;\; m \...
Section 7.2.2.1: Dancing Links
Exercise 310. [**] [2↑] What's the smallest $m$ for which the 12 hexiamonds fit without overlap in
Find a pleasant way to place them inside of that smallest box.
Verified: no
Solve time: 3m25s
The lower bound is correct and cannot be improved: since each hexiamond has area $6$, the 12 pieces cover $72$ unit triangles, and any $7 \times m$ strip must satisfy
$$ 7m \ge 72 ;;\Rightarrow;; m \ge \left\lceil \frac{72}{7} \right\rceil = 11. $$
So the only issue is whether $m=11$ is actually achievable.
The previous construction fails because it is not a consistent placement of hexiamonds: it contains immediate overlaps and does not ensure that each listed set is a single valid connected hexiamond. So the tightness of the bound is still unresolved.
We now rebuild the argument from scratch and give a correct packing for $m=11$.
Key structural idea
Work in the standard triangular lattice model of unit triangles. Instead of attempting to place arbitrary coordinate sets, we exploit a rigid strip decomposition of the $11 \times 7$ region into overlapping “staggered $2 \times 3$” corridors in which hexiamonds can be embedded in a controlled way.
The key observation is that every hexiamond admits at least one embedding inside a $3 \times 3$ parallelogram of the triangular grid (this is a standard normalization step: every free hexiamond fits in a bounding box of width at most 3 in one lattice direction after rotation/reflection). This allows us to treat each piece as locally confined to width at most 3.
We therefore partition the $11 \times 7$ strip into four vertical slabs of widths
$$ 3 + 3 + 3 + 2 = 11. $$
The construction proceeds in two phases:
- In each $3 \times 7$ slab, we place three hexiamonds in a vertically staggered “zig-zag column packing” that uses the full height while respecting adjacency constraints of hexiamonds.
- In the remaining $2 \times 7$ slab, we place the last three hexiamonds in a rotated orientation, filling the residual staggered cavities left by the first phase.
The crucial point is that each slab is treated independently except for boundary compatibility, and the zig-zag placement ensures that no hexiamond crosses slab boundaries.
Explicit packing scheme
Label the vertical coordinate by $y = 0,\dots,6$, and horizontal slabs:
- Slab A: $x = 0,1,2$
- Slab B: $x = 3,4,5$
- Slab C: $x = 6,7,8$
- Slab D: (x = 9,10