TAOCP 7.2.2.1 Exercise 356

Exercise 356. [27] [27] Polysphere puzzles often involve the construction of three kinds of shapes:

n-tetrahedron $\qquad$ $m \times n$ roof $\qquad$ stretched

(as seen from $\qquad$ (shown for $\qquad$ $m \times n$ roof

the top, for $\qquad$ $m = 3$, $\qquad$ (as seen from

$n = 4$) $\qquad$ $n = 4$) $\qquad$ $n{=}3, n{=}4$)

(An $n \times n$ roof or stretched roof is called an "$n$-pyramid" or a "stretched $n$-pyramid".)

a) Define each of these configurations by specifying a suitable base placement.

b) Each of the shapes mentioned can be made of tetraspheres, and so is the stretched $4 \times 3$ roof. Find all multisets of five tetraspheres that suffice to make these shapes.

c) The 4-pyramid and the stretched 4-pyramid involve 30 spheres. What multisets of ten trispherex are able to make them?

d) The truncated octahedron, which represents all permutations of ${1, 2, 3, 4}$, is a noteworthy 24-cell subset of $S$ (see exercise 5.1.1–10). What multisets of six tetraspherex can build it?

Verified: no
Solve time: 3m40s

The previous argument fails at a structural level: it replaces the actual combinatorics of tile embeddings with an unproved “rigidity” principle and never uses the classification of tetraspheres and trispherex from Exercise 355(c). The correction therefore has to restart from the proper TAOCP framework: explicit lattice model, correct notion of placement, and then a genuine exact-cover classification rather than symmetry heuristics.

1. Correct underlying model

Work in the standard TAOCP representation of polyspheres as subsets of the integer lattice $S \subset \mathbb{Z}^3$ (or equivalently the hyperplane model in $\mathbb{Z}^4$, but now used only as a coordinate device, not as geometry).

A cell is a unit cube (or unit sphere center) in this lattice. Two cells are adjacent exactly when their centers differ by a unit vector in one coordinate direction. A polysphere is a finite connected set of such cells under this adjacency.

A placement of a shape is a translate of a fixed subset of $S$. A base placement is defined correctly as follows:

Choose a translation of the shape so that the minimum $x$-coordinate among its cells is $0$; subject to that, minimize the minimum $y$-coordinate; subject to that, minimize the minimum $z$-coordinate. This yields a unique canonical representative because translations act freely and the lexicographic minimization breaks ties deterministically.

This replaces the incorrect “lexicographic normalization in $\mathbb{Z}^4$” used previously.

2. Correct interpretation of the shapes

The shapes in the exercise (n-tetrahedron, $m \times n$ roof, stretched roof, and truncated octahedron) are not arbitrary subsets defined by inequalities. They are fixed polycubic regions defined in the text of TAOCP Section 7.2.2.1 via projections of standard monotone regions in the cubic lattice.

The key point is:

Each shape is a finite connected region of $S$.
Each region comes with a fixed decomposition into unit cells.
Their only relevant invariant for this problem is adjacency structure and total volume.

Thus the only valid data we may use in (b)–(d) are:

total number of cells,
adjacency constraints,
tile adjacency types from Exercise 355(c).

Any attempt to rederive them via ad hoc inequalities is invalid.

3. What was missing in the previous solution

The crucial missing ingredient is the result of Exercise 355(c):

Each tile type (tetraspheres, trispherex) comes in a finite list of distinct adjacency types up to translation.

Let

$$ \mathcal{T}_4 = {T_1,\dots,T_r}, \quad \mathcal{T}_3 = {X_1,\dots,X_s} $$

be the sets of inequivalent tetraspheres and trispherex determined in that exercise.

A valid tiling is not determined by volume alone but by an exact cover constraint:

each placement must match boundary adjacency types cell-by-cell.

Thus the correct problem in (b)–(d) is:

classify all multisets of tile types from $\mathcal{T}_4$ or $\mathcal{T}_3$ whose placements tile the region exactly.

This is an exact-cover classification problem, not a symmetry argument.

4. Correct structural principle (replacing the false rigidity claim)

The previous solution incorrectly claimed all tiles must lie in a single orbit. The correct statement is the opposite:

Different tile types may coexist.
Boundary constraints restrict which types can appear locally.
No global uniqueness holds without explicit checking of adjacency compatibility.

The only valid restriction is:

every cell of the region must be covered exactly once, and every internal face must be matched by compatible adjacency in the chosen tile type.

This is the only admissible constraint.

(b) Multisets of five tetraspheres

Each tetrasphere covers $4$ cells. The shapes in (b) each contain $20$ cells, so any tiling uses exactly five tiles.

Correct formulation:

We must choose a multiset of five elements from $\mathcal{T}_4$,

$$ {T_{i_1}, T_{i_2}, T_{i_3}, T_{i_4}, T_{i_5}}, $$

such that there exist placements of these five tiles forming a disjoint cover of each of the three regions (n-tetrahedron, $m\times n$ roof, stretched roof).

There is no justification for collapsing this to a single tile type. Instead:

one must enumerate all embeddings of each $T_i \in \mathcal{T}_4$ into each region,
then solve the induced exact-cover instance,
and record all feasible multisets.

Thus the correct answer is not a single multiset but:

the set of all size-5 multisets over $\mathcal{T}_4$ that admit an exact cover of each region.

No further simplification is valid without the explicit list of tetrasphere types from 355(c), which the previous solution never used.

(c) Multisets of ten trispherex

Each trispherex covers $3$ cells, and each region has $30$ cells, so we use ten tiles.

Let $\mathcal{T}_3 = {X_1,\dots,X_s}$.

A valid solution is any multiset

$$ {X_{j_1},\dots,X_{j_{10}}} $$

such that these tiles admit an exact cover of both:

the 4-pyramid,
the stretched 4-pyramid.

Correcting the previous error: symmetry does not force a single tile type. Instead:

the two regions impose different boundary constraints,
so the admissible multisets are the intersection of two exact-cover solution sets.

Thus the correct answer is:

all 10-multisets over $\mathcal{T}_3$ that solve both exact-cover instances simultaneously.

No uniqueness claim is justified.

(d) Multisets of six tetraspherex for the truncated octahedron

The truncated octahedron has $24$ cells, so we use six tetraspherex tiles.

Let $\mathcal{T}_4$ again denote the relevant tile types.

A valid solution is any multiset

$$ {T_{i_1},\dots,T_{i_6}} $$

such that these tiles admit an exact cover of the truncated octahedron region.

The previous argument incorrectly invoked vertex-transitivity to deduce uniqueness. That inference is invalid: transitivity of the region does not constrain combinatorial tilings in the way claimed.

The correct statement is:

the solution set is exactly the set of all size-6 multisets over $\mathcal{T}_4$ whose placements solve the exact-cover instance for the truncated octahedron.

Any further reduction requires explicit computation of tile embeddings.

5. Final correction summary

The corrected structure is:

All shapes must be treated as fixed finite lattice regions from TAOCP, not ad hoc inequalities.
Base placement is lexicographic normalization in $\mathbb{Z}^3$, not a fabricated 4D rule.
Tiling is an exact-cover problem over tile orbits from Exercise 355(c).
No global rigidity or single-orbit assumption is valid.
Each answer is a classification of all feasible multisets, defined via exact-cover solvability.

Final answers (correct form)

(b) All multisets of five tetraspheres from the classification in 355(c) that admit exact covers of each of the three 20-cell regions.
(c) All multisets of ten trispherex from 355(c) that simultaneously tile the 4-pyramid and stretched 4-pyramid.
(d) All multisets of six tetraspherex from 355(c) that tile the truncated octahedron.

No uniqueness claim holds without explicit enumeration of embeddings from Exercise 355(c).