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: 4m27s

A complete solution to Exercise 7.2.2.1.383 cannot be written from the information supplied here alone, because the actual coordinate data from Exercise 382 are essential.

The flawed solution failed precisely at the point where it replaced the concrete $7\times7\times7$ motley dissection by an abstract family of $23$ cuboids. To construct the required $92\times92\times92$ cube, one must know the actual triples

$$ [a_r,b_r)\times[c_r,d_r)\times[e_r,f_r), \qquad 1\le r\le23, $$

from Exercise 382. Without those intervals, it is impossible to verify that the stretching preserves the required combinatorial pattern, impossible to detect repeated dimension forms, and impossible to list the resulting $69$ integer dimensions.

The corrected argument has the following form once the Exercise 382 coordinates are available.

Let the seven intervals on the three axes be assigned lengths

$$ X_1,\ldots ,X_7,\qquad Y_1,\ldots ,Y_7,\qquad Z_1,\ldots ,Z_7, $$

with

$$ \sum_{i=1}^7X_i= \sum_{i=1}^7Y_i= \sum_{i=1}^7Z_i=92 . $$

For the $r$-th cuboid of Exercise 382, the three new side lengths are

$$ A_r=\sum_{i=a_r+1}^{b_r}X_i , $$

$$ B_r=\sum_{i=c_r+1}^{d_r}Y_i , $$

$$ C_r=\sum_{i=e_r+1}^{f_r}Z_i . $$

The task is to choose the $21$ positive integers $X_i,Y_i,Z_i$ so that the multiset

$$ {A_r,B_r,C_r:1\le r\le23} $$

contains $69$ distinct elements.

The construction cannot be replaced by the invalid hyperplane argument in the previous solution. The correct procedure is finite and explicit:

Obtain the $23$ coordinate intervals from Exercise 382.
Compute the $69$ linear forms in the $21$ variables

$$ X_1,\ldots ,X_7,Y_1,\ldots ,Y_7,Z_1,\ldots ,Z_7 . $$ 3. Check that no two of these forms are identical. If two forms are identical, no stretching can ever produce a perfectly decomposed cube. 4. Search the finite set of positive compositions

$$ X_1+\cdots+X_7=92, $$

and similarly for $Y$ and $Z$, until a triple of compositions is found for which all $69$ evaluated forms are different. 5. Verify the resulting list of $69$ dimensions explicitly.

The final answer must therefore contain three concrete rows

$$ (X_1,\ldots ,X_7), \qquad (Y_1,\ldots ,Y_7), \qquad (Z_1,\ldots ,Z_7), $$

followed by the $23$ triples

$$ (A_r,B_r,C_r), $$

with all $69$ entries distinct.

Those numerical data are not present in the proposed solution or in the reviewer feedback. Supplying a purported construction without the Exercise 382 coordinates would amount to inventing the missing verification. The corrected solution requires the actual $7\times7\times7$ dissection data from Exercise 382.