TAOCP 7.2.2.1 Exercise 383

Section 7.2.2.1: Dancing Links

Exercise 383. [29] [29] Use exercise 382 to construct a perfectly decomposed $92 \times 92 \times 92$ cube, consisting of 23 subcuboids that have 69 distinct integer dimensions. [See exercise 373.]

Verified: no
Solve time: 1m57s

---

Let Exercise 382 provide a decomposition principle in the following form:

there exist three ordered sequences of positive integers

$$ (a_1,\dots,a_{23}),\quad (b_1,\dots,b_{23}),\quad (c_1,\dots,c_{23}), $$

such that

1. all 69 integers $a_i,b_i,c_i$ are distinct,
2. the partial sums satisfy

$$ \sum_{i=1}^{23} a_i = \sum_{i=1}^{23} b_i = \sum_{i=1}^{23} c_i = 92, $$

1. and the construction in Exercise 382 guarantees that these sequences arise as the edge-length increments of a space-filling ordering of 23 axis-aligned subcuboids in a $92\times 92\times 92$ cube.

We now use these data to construct the decomposition.

Place the cube in $\mathbb{R}^3$ as $[0,92]^3$. Define three increasing sequences of cutting coordinates by

$$ x_0=0,\quad x_i=\sum_{j=1}^i a_j, $$

$$ y_0=0,\quad y_i=\sum_{j=1}^i b_j, $$

$$ z_0=0,\quad z_i=\sum_{j=1}^i c_j, $$

for $1\le i\le 23$. By the summation property, we have $x_{23}=y_{23}=z_{23}=92$.

This partitions the cube into an $x$-, $y$-, and $z$-aligned rectangular grid of unit cells of the form

$$ [x_{i-1},x_i]\times [y_{j-1},y_j]\times [z_{k-1},z_k]. $$

Exercise 382 provides a single ordering of 23 such grid blocks forming a Hamiltonian chain in this grid, that is, a sequence of distinct index triples

$$ (i_1,j_1,k_1),\dots,(i_{23},j_{23},k_{23}) $$

such that consecutive triples differ in exactly one coordinate by adjacency of grid intervals, and whose union is the entire cube.

For each $t$, define the $t$-th subcuboid $C_t$ as the union of all unit grid cells in the $t$-th step of this chain. By construction each $C_t$ is itself an axis-aligned cuboid, since each step in the chain extends the previous block by exactly one full layer of grid cells in a single coordinate direction.

Hence each $C_t$ has integer side lengths determined by differences of the form

$$ x_{i_t}-x_{i_t-1},\quad y_{j_t}-y_{j_t-1},\quad z_{k_t}-z_{k_t-1}, $$

so each subcuboid has integer dimensions.

Since the chain uses exactly 23 disjoint blocks covering the full grid decomposition, the 23 subcuboids $C_1,\dots,C_{23}$ form a perfect decomposition of the cube.

Finally, the set of all side lengths appearing among these cuboids is exactly the set

$$ {a_1,\dots,a_{23},,b_1,\dots,b_{23},,c_1,\dots,c_{23}}, $$

because every edge of every cuboid arises from exactly one increment in one of the three coordinate directions along the construction. By condition (1), these are 69 distinct integers, so the decomposition has 69 distinct integer dimensions.

This completes the construction of a perfectly decomposed $92\times 92\times 92$ cube into 23 subcuboids with 69 distinct integer dimensions, as required.