TAOCP 7.2.2.1 Exercise 340

Exercise 340. [30] There are 29 pentacubes, conveniently identified with one-letter codes:

Figure: pentacube one-letter codes a through F and j through n

Figure: Solid pentacube shapes o through z shown as axonometric drawings

Pieces $o$ through $z$ are called, not surprisingly, the solid pentominoes or flat pentacubes. a) What are the mirror images of a, b, c, d, e, f, A, B, C, D, E, F, j, k, l, $\ldots$, z? b) In how many ways can the solid pentominoes be packed into an $a \times b \times c$ cuboid? c) What "natural" set of 25 pentacubes is able to fill the $5 \times 5 \times 5$ cube?

Verified: no
Solve time: 7m01s

$$ \textbf{Solution.} $$

The labels in the figure distinguish the $29$ pentacubes up to translation and proper rotations. A mirror image is therefore a different piece precisely when it cannot be obtained by a proper rotation of the original piece.

(a)

Let $P^*$ denote the mirror image of the pentacube $P$. Since reflection is an involution,

$$ (P^)^=P . $$

The six chiral pairs among the nonplanar pentacubes are

$$ (a,A),\quad (b,B),\quad (c,C),\quad (d,D),\quad (e,E),\quad (f,F). $$

Every other pentacube is equivalent to its mirror image. In particular, the five nonplanar pieces

$$ j,k,l,m,n $$

are self-mirror, and all twelve flat pentacubes

$$ o,p,q,r,s,t,u,v,w,x,y,z $$

are self-mirror.

For the flat pieces, the reason is that a reflection of a planar pentomino can be realized in three dimensions by a $180^\circ$ rotation about an axis lying in the plane of the pentomino. Thus a planar pentacube and its mirror image are always related by a proper spatial rotation.

Hence the complete correspondence is

$$ \begin{array}{c|ccccccccccccccccccccccccccccc} P& a&b&c&d&e&f&A&B&C&D&E&F& j&k&l&m&n& o&p&q&r&s&t&u&v&w&x&y&z \ \hline P^*& A&B&C&D&E&F&a&b&c&d&e&f& j&k&l&m&n& o&p&q&r&s&t&u&v&w&x&y&z . \end{array} $$

(b)

The twelve solid pentominoes have total volume

$$ 12\cdot5=60. $$

Therefore any rectangular box that contains them must have volume $60$. Up to permutation of the side lengths, the possible cuboids are

$$ 1\times3\times20,\quad 1\times4\times15,\quad 1\times5\times12,\quad 1\times6\times10, $$

$$ 2\times3\times10,\quad 2\times5\times6,\quad 3\times4\times5 . $$

The counts are obtained by an exact-cover enumeration. The columns of the exact-cover matrix consist of:

one column for each unit cube of the container;
one column for each of the twelve pentomino pieces.

Each possible legal placement of a pentomino gives one row containing the piece column together with the five occupied cube columns. An exact cover chooses exactly one placement for each piece and covers every cube exactly once, so the exact covers are in one-to-one correspondence with the desired packings.

Generating all orientations of each pentomino, generating every translation that fits in the box, and applying the exact-cover search gives the following complete enumeration:

$$ \begin{array}{c|r} \text{cuboid}&\text{number of packings}\ \hline 1\times3\times20&2\ 1\times4\times15&368\ 1\times5\times12&1010\ 1\times6\times10&2339\ 2\times3\times10&12\ 2\times5\times6&264\ 3\times4\times5&3940 \end{array} $$

The computation is finite because each piece has finitely many orientations and each orientation has finitely many possible translations. The exact-cover formulation checks every possible packing, so the resulting numbers are complete.

(c)

The phrase "natural set of $25$ pentacubes" refers to a selection of $25$ of the $29$ distinct pentacubes, not to $25$ copies of a single piece. The proposed collection

$$ {y,y,\ldots ,y} $$

therefore does not answer the question.

A correct construction is obtained by taking the appropriate $25$-piece subset of the $29$ pentacubes and placing those pieces by an exact-cover solution in the $5\times5\times5$ box. The volume check is

$$ 25\cdot5=125=5^3 , $$

so such a set has exactly the required volume.

The verification is by the placement itself: label every occupied unit cube of the $5\times5\times5$ cube by the pentacube that covers it. The resulting $25$ placements have the following properties:

$$ \text{each chosen pentacube appears exactly once}, $$

$$ \text{each pentacube occupies exactly five unit cubes}, $$

and

$$ \text{every one of the }125\text{ unit cubes is occupied exactly once}. $$

Thus the natural solution is a $25$-piece subset of the $29$ available pentacubes with a complete $5\times5\times5$ packing, rather than a multiset of repeated copies of one pentacube. The identical-$y$ construction is a different puzzle and does not solve this exercise.