Trihex Packing on a Triangular Tower (Hex Grid)
Question
We work on the hexagonal grid, modeled in axial coordinates by the lattice
$$ \Lambda := \mathbb{Z}^2, $$with adjacency given by the six step vectors
$$ (\pm 1,0),\ (0,\pm 1),\ (\pm 1,\mp 1). $$Equivalently, we view $\Lambda$ as the vertex set of a graph (the hex-cell adjacency graph) in which $(i,j)$ is adjacent to $(i',j')$ if and only if $(i'-i,j'-j)$ is one of the above vectors.
Triangular tower region
Definition 1 (Triangular tower). For $n\in \mathbb{Z}_{\ge 1}$ define the (upward) triangular tower region
$$ T_n := \{(i,j)\in \Lambda:\ i\ge 0,\ j\ge 0,\ i+j\le n-1\}. $$Then $T_n$ has $n$ anti-diagonal layers (rows) of sizes $1,2,\dots,n$, hence
$$ |T_n|=\sum_{r=1}^n r=\frac{n(n+1)}{2}. $$Trihex tiles
Definition 2 (Trihex / 3-hex tile). A trihex tile is any translate of one of the following 3-cell patterns:
$$ U_{p,q}:=\{(p,q),(p+1,q),(p,q+1)\}, $$$$ D_{p,q}:=\{(p+1,q+1),(p+1,q),(p,q+1)\}, $$provided all three cells lie in the region of interest. Two tiles are disjoint if they share no cell.
Regular hexagon region (axial coordinates)
Definition 3 (Regular hexagon). For $n\in \mathbb{Z}_{\ge 1}$ let
$$ H_n := \{(i,j)\in \Lambda: -n+1\le i\le n-1,\ -n+1\le j\le n-1,\ -n+1\le i+j\le n-1 \}. $$This is the regular hexagon of side length $n$ in axial coordinates, and its size is
$$ |H_n| = 3n(n-1)+1. $$Problems (triangular tower)
(Generated by scripts/generate_trihex_tower_illustration.py.)
Problem 1 (Maximal trihex packing on $T_n$). For $n\ge 1$, let $M_T(n)$ be the maximum number of pairwise-disjoint trihex tiles that can be placed inside $T_n$.
Determine $M_T(n)$ as a function of $n$.
Characterise those $n$ for which a perfect tiling exists, i.e.
$$ 3M_T(n)=|T_n|. $$When a perfect tiling does not exist, determine the minimum number of uncovered cells, i.e.
$$ |T_n|-3M_T(n). $$
Problem 2 (Decision version on $T_n$). Given $n\ge 1$ and an integer $k$, decide whether there exist $k$ disjoint trihex tiles in $T_n$. Equivalently, decide whether $M_T(n)\ge k$.
Problem 3 (Single-hole placement set on $T_n$). Suppose $n$ is such that every optimal packing leaves exactly one uncovered cell. Let $H_T(n)\subseteq T_n$ be the set of cells that can occur as the unique hole in some optimal packing.
Describe $H_T(n)$ explicitly (e.g. in terms of a $3$-colouring class).
Under the standard $3$-colouring
$$ c(i,j)\equiv i-j \pmod 3, $$decide whether $H_T(n)$ equals the entire majority colour class.
(Local move connectivity) Prove that any two optimal packings with holes in $H_T(n)$ are connected by a sequence of local flips that slide the hole within $H_T(n)$.
Problem 4 (Constructive algorithm on $T_n$). Design an algorithm that, given $n$, constructs an optimal packing in time $O(n^2)$.
- If perfect tilings exist for that $n$, the algorithm should output one.
- Otherwise it should output a packing with the minimum possible number of uncovered cells.
- Optionally, allow the hole to be placed at a prescribed admissible location (if possible).
Problems (regular hexagon)
Problem 5 (Maximal trihex packing on $H_n$). For $n\ge 1$, let $M_H(n)$ be the maximum number of pairwise-disjoint trihex tiles that can be placed inside $H_n$.
- Determine $M_H(n)$ as a function of $n$.
- Decide whether a perfect tiling is ever possible; if not, determine the minimum number of uncovered cells (as a function of $n$) and give explicit constructions achieving it.
Problem 6 (Hole placement on $H_n$). When every optimal packing of $H_n$ leaves exactly one uncovered cell, characterise the set of cells that can occur as the unique hole. In particular:
- Decide whether the centre cell is always attainable.
- Decide whether every majority-colour cell is attainable via local flips.
Intuition (structural “strip” gadgets)
The following is intended as structure/heuristics for building packings; proofs and optimality arguments are intentionally omitted here.
Antidiagonal bands
For integers $a\ge 0$, define the height-$3$ and height-$2$ antidiagonal bands
$$ S_a := \{(i,j)\in T_n:\ a\le i+j\le a+2\}, $$$$ B_a := \{(i,j)\in T_n:\ a\le i+j\le a+1\}. $$Within $T_n$, their top/bottom layer sizes (when fully present) are
$$ |{\rm top}(S_a)|=a+1,\qquad |{\rm bot}(S_a)|=a+3, $$$$ |{\rm top}(B_a)|=a+1,\qquad |{\rm bot}(B_a)|=a+2. $$Gadget A (3-layer “even–even” brick)
Gadget A (candidate local tiling). A $2\times 3$ rhombus (two columns across, three rows tall) can be tiled by exactly two disjoint trihexes, one of type $U$ and one of type $D$. Stacking such rhombi partitions certain 3-layer bands into disjoint bricks.
- Legend: blue = one trihex tile, orange = the other trihex tile (disjoint).
Gadget B (2-layer “tail + 2×3 blocks”)
Gadget B (candidate local tiling). A 2-layer band whose row lengths are
$$ (a+1,a+2)=(1+3k,\,2+3k) $$admits a decomposition into $k$ disjoint $2\times 3$ rhombi plus a leftmost $(1,2)$ “tail”, where the tail is itself exactly one trihex.
- Legend: green = the $(1,2)$ tail trihex, blue/orange = the two trihexes tiling the remaining $2\times 3$ brick (all disjoint).
Necessary bounds from the 3-colouring
Define the standard $3$-colouring of $\Lambda$ by
$$ c(i,j)\equiv i-j \pmod 3,\qquad c(i,j)\in \{0,1,2\}. $$Lemma: every trihex uses all three colours
Lemma. Every trihex tile (of type $U$ or $D$) contains exactly one cell of each colour class under $c$.
Proof. For $U_{p,q}=\{(p,q),(p+1,q),(p,q+1)\}$ we have
$$ c(p+1,q)\equiv c(p,q)+1,\qquad c(p,q+1)\equiv c(p,q)-1\pmod 3, $$so the three colours are all distinct. For $D_{p,q}=\{(p+1,q+1),(p+1,q),(p,q+1)\}$ we have
$$ c(p+1,q)\equiv c(p,q+1)+2,\qquad c(p+1,q+1)\equiv c(p,q+1)+1\pmod 3, $$again giving three distinct residues. $\square$
(1) An unavoidable $|T_n|\bmod 3$ constraint
Since $|T_n|=\frac{n(n+1)}{2}$, we get
$$ |T_n|\equiv \begin{cases} 1 \pmod 3, & n\equiv 1 \pmod 3,\\ 0 \pmod 3, & n\equiv 0,2 \pmod 3. \end{cases} $$Consequently:
- If $n\equiv 1\pmod 3$, then a perfect tiling is impossible, and every packing leaves at least one uncovered cell.
- If $n\equiv 0,2\pmod 3$, then the number of uncovered cells must be a multiple of $3$ (i.e. $0,3,6,\dots$).
(2) Colour-counting bounds (necessary, not sufficient)
Let
$$ A_r(n):=\#\{(i,j)\in T_n:\ c(i,j)=r\},\qquad r\in\{0,1,2\}. $$By the lemma, each placed trihex consumes one cell from each colour class, hence
$$ M_T(n)\le \min_{r\in\{0,1,2\}} A_r(n), $$and therefore any packing leaves at least
$$ |T_n|-3\min_{r}A_r(n) $$uncovered cells.
Explicit colour counts in $T_n$
Layer $T_n$ by antidiagonals $i+j=t$ for $t=0,1,\dots,n-1$. On a fixed layer, writing $(i,j)=(i,t-i)$, we have
$$ c(i,t-i)\equiv 2i-t\pmod 3, $$so colours along the layer repeat periodically with period $3$, and the three colour counts on that layer differ by at most $1$. Summing over layers yields:
$$ (A_0(n),A_1(n),A_2(n))= \begin{cases} \left(\dfrac{n(n+1)+4}{6},\ \dfrac{n(n+1)-2}{6},\ \dfrac{n(n+1)-2}{6}\right), & n\equiv 1 \pmod 3,\\[10pt] \left(\dfrac{n(n+1)}{6},\ \dfrac{n(n+1)}{6},\ \dfrac{n(n+1)}{6}\right), & n\equiv 0,2 \pmod 3. \end{cases} $$In particular,
$$ A_0(n)=A_1(n)=A_2(n)\quad \Longleftrightarrow\quad n\not\equiv 1\pmod 3. $$The $n\equiv 1\pmod 3$ case: forced defect $\ge 1$ (and a natural conjecture)
Define the defect
$$ r(T_n):=|T_n|-3M_T(n), $$so that $r(T_n)=0$ is equivalent to a perfect tiling, and in general $r(T_n)$ is the minimum possible number of uncovered cells in $T_n$.
Proposition (rigorous). If $n\equiv 1\pmod 3$, then
$$ M_T(n)\le \frac{|T_n|-1}{3}=\frac{n(n+1)-2}{6}, \qquad\text{equivalently}\qquad r(T_n)\ge 1. $$Proof. When $n\equiv 1\pmod 3$, the explicit colour counts above give
$$ (A_0(n),A_1(n),A_2(n))=\left(\frac{n(n+1)+4}{6},\ \frac{n(n+1)-2}{6},\ \frac{n(n+1)-2}{6}\right), $$so $\min_r A_r(n)=\frac{n(n+1)-2}{6}$. Since each trihex consumes exactly one cell of each colour, any packing satisfies
$$ M_T(n)\le \min_r A_r(n)=\frac{n(n+1)-2}{6}, $$which implies
$$ r(T_n)=|T_n|-3M_T(n)\ge \frac{n(n+1)}{2}-3\cdot\frac{n(n+1)-2}{6}=1. $$$\square$
Conjecture (likely true, proof welcome). If $n\equiv 1\pmod 3$, then the bound above is tight, i.e.
$$ M_T(n)=\frac{|T_n|-1}{3} \qquad\text{and}\qquad r(T_n)=1. $$Write $n=3m+1$. Consider the hole position $(m,m)\in T_n$ (note $c(m,m)\equiv 0$, the majority colour). A very natural guess (supported by many small-$n$ constructions) is that $T_n\setminus\{(m,m)\}$ always admits a perfect trihex tiling.
Computational evidence (small $n$)
I checked this by exact-cover backtracking (same style of search used to generate the $T_{14}$ picture above):
- For $n=3m+1$ (i.e. $n\equiv 1\pmod 3$), a tiling of $T_n\setminus\{(m,m)\}$ was found for every $2\le n\le 30$ (equivalently $1\le m\le 9$). For $n\equiv 0,2\pmod 3$ the plot below also attempts a perfect tiling (defect $0$) and reports success/failure within a fixed node limit (so: computational evidence, not a proof).
In addition, for $1\le n\le 16$ the plot uses a saved table of minimal holes (exact optimum values) generated by a separate search run.
You can reproduce (or extend) this plot by running:
python scripts/build_plots.py.
Gallery: all $n\equiv 1\pmod 3$ examples for $2\le n\le 30$
Tn \ {(m,m)} with n=3m+1 and hole at the center.
(Generated by scripts/generate_trihex_tower_hole_illustration.py.)
Construction template (needs a clean write-up). A plausible approach is a deterministic $\Theta(n^2)$ scanline/strip tiling based on the local bricks pictured above:
- Gadget A: a $2\times 3$ rhombus tiled by two disjoint trihexes.
- Gadget B: a $2$-level band $B_a=\{(i,j)\in T_n: a\le i+j\le a+1\}$ with row lengths $(1+3k,2+3k)$ decomposed into $k$ copies of Gadget A plus a single “tail” trihex.
If you can supply an explicit coordinate-level decomposition for all $m$ (or a short inductive construction), that would turn the conjecture into a full proof.
What a proof likely needs (informal sketch)
An “obvious” induction by stripping a fixed-width boundary fails because the required missing cell changes from $(m-1,m-1)$ to $(m,m)$ as $n$ grows from $3(m-1)+1$ to $3m+1$.
A plausible route is to combine:
- Strip tiling step: a deterministic tiling of the outer $3$ antidiagonal layers (using Gadgets A/B) so that what remains is isomorphic to a smaller triangular tower.
- Hole-shift lemma: a bounded local retile (“local flip”) that moves the unique hole by $(1,1)$ along the diagonal, without affecting cells far away.
Together these would let you induct: tile the outer strip, then locally “slide” the hole to the new centre.
Remarks.
- When $n\equiv 1\pmod 3$, the colour-counting bound already forces at least one hole (and the majority class is colour $0$).
- When $n\not\equiv 1\pmod 3$, the colour counts do not obstruct a perfect tiling, but this necessary condition is not sufficient (e.g. some $n$ may still fail to tile perfectly even though the counts balance).
What can we answer now (and what’s open)
This post is intentionally split into:
- Answerable / proved facts for $T_n$ (below).
- Hard or genuinely open pieces (left as problems for others).
Answerable now (proved in this post)
- Mod-3 obstruction: if $n\equiv 1\pmod 3$, then $r(T_n)\ge 1$ (no perfect tiling).
- Divisibility constraint: if $n\equiv 0,2\pmod 3$, then $r(T_n)\equiv 0\pmod 3$.
- Sharp colour-count upper bound for $n\equiv 1\pmod 3$: $$ M_T(n)\le \frac{n(n+1)-2}{6}. $$
Open / leave space
- Tightness for $n\equiv 1\pmod 3$: prove (or refute) that $r(T_n)=1$ for all such $n$ (equivalently, that $T_n\setminus\{(m,m)\}$ always tiles for $n=3m+1$).
- Exact values for $n\equiv 0,2\pmod 3$: determine when $r(T_n)=0$ vs $3$ vs larger.
- Problem 3 (hole set $H_T(n)$) + local-move connectivity: characterise reachable holes and prove flip-connectivity.
- Problems on $H_n$: these look substantially harder; even basic exact formulas may require new ideas.
Why general regions get hard (context only)
For arbitrary finite regions in the hex grid, trihex tiling/packing problems can encode constraint satisfaction via gadgets, so decision/maximisation versions are NP-hard in general. The family $T_n$ is much more structured (one parameter), so some subquestions remain tractable/attackable here even though the general problem is computationally hard.