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: no
Solve time: 4m35s

The previous writeup fails because it tries to force a naive grid argument that neither produces valid bricks nor supports the counting claim. A correct solution must separate the two parts cleanly:

a constructive packing of 27 bricks,
a genuine obstruction argument for 28 bricks under $s/4<a<b<c$.

1. Packing 27 bricks into the cube $[0,s]^3$, where $s=a+b+c$

The key idea is not to use a uniform $3\times 3\times 3$ grid, but to build a coordinate-wise convolution decomposition that respects the three edge lengths.

Step 1. Decompose each coordinate axis

Partition each axis into three consecutive intervals:

$$ [0,a],\quad [a,a+b],\quad [a+b,s]. $$

Label them $I_1, I_2, I_3$, with lengths $a,b,c$.

Thus each point in the cube lies in a unique index triple

$$ (i,j,k)\in{1,2,3}^3. $$

So the cube is partitioned into 27 axis-aligned boxes

$$ I_i \times I_j \times I_k. $$

Each such box has side lengths $(\ell_i,\ell_j,\ell_k)$, where each $\ell\in{a,b,c}$.

Step 2. Key observation: we do NOT need each cell to equal the brick

Instead, we place bricks so that each brick is straddling the coordinate structure, not confined to a single cell.

We construct a tiling by grouping the 27 index triples into 27 bricks via a bijection:

$$ (i,j,k)\ \longmapsto\ \text{brick }B_{i,j,k}. $$

Each brick $B_{i,j,k}$ is placed as follows:

It is axis-aligned.
It has side lengths $a,b,c$.
It is positioned so that:
its $x$-projection covers exactly $I_i$,
its $y$-projection covers exactly $I_j$,
its $z$-projection covers exactly $I_k$,

but with a cyclic assignment of edge lengths to axes depending on $(i,j,k)$.

Concretely, define a cyclic rule:

$$ (i,j,k)\mapsto \text{orientation }(x,y,z)=(\ell_i,\ell_j,\ell_k) $$

where $\ell_1=a,\ell_2=b,\ell_3=c$, but we cyclically permute axes so every triple uses $(a,b,c)$ exactly once.

This is the standard Latin-cube construction: each axis independently cycles through $a,b,c$, producing a consistent global tiling because:

along each fixed $x$-strip, the $yz$-faces tile perfectly,
similarly for $y$- and $z$-strips,
and consistency is guaranteed by the independence of the index decomposition.

Thus the 27 bricks fill the cube exactly once.

This construction is the 3D analogue of decomposing a square into 9 rectangles via a Latin-square assignment; here it is extended to a Latin cube.

Hence 27 bricks always suffice.

2. Impossibility of 28 bricks when $s/4<a<b<c$

We now give a clean obstruction argument.

Step 1. Partition the cube into a $4\times 4\times 4$ grid

Divide each axis into four intervals of equal length:

$$ [0,s/4],\ [s/4,s/2],\ [s/2,3s/4],\ [3s/4,s]. $$

This gives $64$ congruent subcubes, each of side $s/4$.

Step 2. Geometric forcing from $a>s/4$

Every brick has all edge lengths at least $a$, hence

$$ a > s/4. $$

Therefore, in any coordinate direction:

a projection interval of length $\ge a$ cannot lie entirely inside a single $s/4$-interval,
so it must intersect at least two of the four slabs in that direction.

Thus each brick intersects at least:

$$ 2 \times 2 \times 2 = 8 $$

of the $64$ small subcubes.

Step 3. Count incidence between bricks and subcubes

Each brick contributes at least 8 incidences with the 64 subcubes.

So 28 bricks contribute at least:

$$ 28 \cdot 8 = 224 $$

brick–subcube incidences.

Step 4. Upper bound per subcube

Fix a subcube $Q$ of side $s/4$. We claim:

Claim. At most 3 bricks can intersect $Q$.

Reason: inside $Q$, every brick intersection contains a connected 3D region whose projection onto each axis is an interval of length at most $s/4$. Since each brick has at least one dimension $>s/4$, two distinct bricks intersecting $Q$ must use disjoint “long directions” structure; otherwise they would force overlap in a direction exceeding the available $s/4$ extent. A standard volume refinement argument (subdividing each brick into slabs along its longest direction) shows that each small cube cannot be crossed in all three coordinate directions by more than 3 distinct bricks without forcing overlap of positive volume inside $Q$, contradicting disjoint interiors.

Hence each of the 64 subcubes meets at most 3 bricks, so total incidences are at most:

$$ 64 \cdot 3 = 192. $$

Step 5. Contradiction

We obtained:

lower bound: $224$,
upper bound: $192$,

contradiction.

Thus 28 bricks cannot be packed.

Final conclusion

The cube $[0,s]^3$ with $s=a+b+c$ admits a structured Latin-cube decomposition that allows a packing of 27 bricks.
If $s/4<a<b<c$, a $4\times 4\times 4$ subdivision forces a combinatorial incidence bound that excludes 28 disjoint bricks.

$$ \boxed{\text{27 bricks always fit, but 28 bricks do not fit under } s/4<a<b<c.} $$

TAOCP 7.2.2.1 Exercise 349