TAOCP 7.2.2.1 Exercise 349
Let s=a+b+c, and consider the cube
Section 7.2.2.1: Dancing Links
Exercise 349. ▶ [M27] [M27] (D. Hoffman.) Show that 27 bricks of size $a \times b \times c$ can always be packed into an $s \times s \times s$ cube, where $s = a + b + c$. But if $s/4 < a < b < c$, 28 bricks won't fit.
Verified: yes
Solve time: 1m53s
Setup
Let
$$ s=a+b+c, $$
and consider the cube
$$ [0,s]^3. $$
The problem has two parts.
- Show that $27$ axis-parallel bricks of dimensions $a\times b\times c$ can always be packed into the cube.
- Show that if
$$ \frac{s}{4}<a<b<c, $$
then no packing of $28$ such bricks exists.
Packing $27$ bricks
Partition each edge of the cube into three consecutive segments of lengths
$$ a,\quad b,\quad c. $$
The three coordinate partitions induce a subdivision of the cube into
$$ 3^3=27 $$
rectangular boxes.
Each subbox has side lengths obtained by choosing one element of ${a,b,c}$ on each coordinate axis. Thus every subbox has dimensions equal to one of the six permutations of
$$ (a,b,c). $$
Since rotations of the bricks are allowed, each subbox is exactly the size of one brick.
The $27$ subboxes tile the cube without overlap, so they give a packing of $27$ bricks.
Impossibility of packing $28$ bricks
Assume now that
$$ \frac{s}{4}<a<b<c, $$
and suppose, for contradiction, that $28$ bricks can be packed into the cube.
Step 1. Interval projections
Fix one coordinate axis, say the $x$-axis.
Each brick projects onto an interval of length equal to one of
$$ a,\ b,\ c, $$
so every projection interval has length strictly greater than
$$ \frac{s}{4}. $$
Consequently, no four projection intervals can be pairwise disjoint, because four pairwise disjoint intervals would have total length exceeding
$$ 4\cdot\frac{s}{4}=s, $$
which is impossible inside an interval of length $s$.
Hence the maximum size of a pairwise disjoint family of projection intervals is at most $3$.
Step 2. Partition into three intersecting families
We now prove that the projection intervals can be partitioned into at most three classes, each class having a common point.
Let $\mathcal I$ be the family of projection intervals.
Construct a graph $G$ whose vertices are the intervals, where two vertices are adjacent exactly when the corresponding intervals are disjoint.
Since no four intervals are pairwise disjoint, the graph $G$ has clique number at most $3$.
The graph $G$ is the complement of the interval graph of $\mathcal I$. Interval graphs are perfect, and the complement of a perfect graph is again perfect. Therefore $G$ is perfect. Hence
$$ \chi(G)=\omega(G)\le3. $$
Thus the vertices of $G$ can be colored with at most three colors.
A color class is an independent set of $G$, so the corresponding intervals are pairwise intersecting.
For intervals on a line, pairwise intersection implies common intersection. This is the one-dimensional Helly property: if every two intervals intersect, then all of them intersect.
Therefore each color class has a point common to all its intervals.
Hence the projection intervals can indeed be partitioned into at most three classes, each having a common point.
Applying the same argument independently to the $y$- and $z$-axes gives analogous partitions for those axes.
Step 3. Pigeonhole argument
For each axis there are at most three classes.
Assign to each brick the triple consisting of its class on the $x$-, $y$-, and $z$-axes.
There are at most
$$ 3^3=27 $$
possible triples.
Since there are $28$ bricks, the pigeonhole principle implies that two distinct bricks receive the same triple.
For each coordinate axis, those two bricks belong to the same class, so their projections both contain the common point of that class. Hence their projections overlap on every coordinate axis.
Two axis-parallel boxes intersect if and only if their projections overlap on each coordinate axis. Therefore these two bricks intersect, contradicting the assumption that the packing is disjoint.
This contradiction shows that no packing of $28$ bricks exists.
Conclusion
The subdivision of the cube into a $3\times3\times3$ grid yields a packing of $27$ bricks.
If
$$ \frac{s}{4}<a<b<c, $$
then every coordinate projection has length exceeding $s/4$. The projection intervals on each axis can therefore be partitioned into at most three families with a common point, yielding at most
$$ 3^3=27 $$
possible class triples. With $28$ bricks, two must share the same triple, forcing them to intersect.
Therefore
$$ \boxed{\text{Every }a,b,c\text{ admit a packing of }27\text{ bricks into the }s\times s\times s\text{ cube},} $$
and, under the additional hypothesis
$$ \frac{s}{4}<a<b<c, $$
$$ \boxed{\text{no packing of }28\text{ such bricks is possible}.} $$