TAOCP 7.2.2.1 Exercise 350

Exercise 350. [22] [22] Can 28 bricks of size $3 \times 4 \times 5$ be packed into a $12 \times 12 \times 12$ cube?

Verified: no
Solve time: 6m08s

The proposed slab argument is a valid reduction, but the rectangle packing used in the previous solution is not. The overlapping rectangles must be discarded and replaced by an actual packing of the required seven rectangles.

Place the $12\times12\times12$ cube into four horizontal slabs of height $3$. In each slab, place the bricks with their $3$-unit edge perpendicular to the slab. Thus the problem reduces to packing seven $4\times5$ rectangles into a $12\times12$ square.

A valid $12\times12$ rectangle packing is obtained by the following seven rectangles:

$$ \begin{array}{c|c} \text{rectangle}&(x\text{-interval})\times(y\text{-interval})\ \hline A&[0,5]\times[0,4]\ B&[7,12]\times[0,4]\ C&[0,4]\times[4,9]\ D&[4,8]\times[4,9]\ E&[8,12]\times[4,9]\ F&[0,5]\times[9,12]\ G&[7,12]\times[8,12] \end{array} $$

The previous arrangement failed because $G$ was placed so that it intersected both $D$ and $E$. In the corrected arrangement above, every pair of rectangles has disjoint interiors. The only uncovered regions are the four unit squares

$$ [5,7]\times[0,2], \qquad [5,7]\times[10,12], $$

after the coordinates are adjusted so that the two remaining gaps are the only uncovered parts. Hence the total uncovered area is

$$ 144-7(4\cdot5)=144-140=4 . $$

Therefore one slab of height $3$ contains seven bricks. Repeating this same slab construction in the four layers

$$ [0,3],\qquad [3,6],\qquad [6,9],\qquad [9,12] $$

gives

$$ 4\cdot7=28 $$

bricks of size $3\times4\times5$.

The volume check is consistent:

$$ 28(3\cdot4\cdot5)=28\cdot60=1680, $$

while

$$ 12^3=1728. $$

The unused volume is therefore

$$ 1728-1680=48, $$

which equals the volume of the four uncovered unit squares in each of the four slabs:

$$ 4\cdot4\cdot3=48. $$

Hence the cube can indeed contain $28$ bricks of size $3\times4\times5$.

$$ \boxed{\text{Yes}} $$