TAOCP 7.2.2.1 Exercise 382

Section 7.2.2.1: Dancing Links

Exercise 382. [18] [18] There's a natural way to extend the idea of motley dissection to three dimensions, by subdividing an $l \times m \times n$ cuboid into subcuboids $(a_i, b_i) \times [c_i, d_i) \times [e_i, f_i)$ that have no repeated intervals $[a_{\cdot}, b_{\cdot})$ or $[c_{\cdot}, d_{\cdot})$ or $[e_{\cdot}, f_{\cdot})$.

For example, Scott Kim has discovered a remarkable motley $7 \times 7 \times 7$ cube, built from 23 individual blocks $1 \times 1$ of which are illustrated here. (Two of them are hidden behind the others.) The full cube is obtained by suitably placing a mirror image of these pieces in front, together with a $1 \times 1 \times 1$ cube in the center.

By studying this picture, show that Kim's construction can be defined by coordinate intervals $[a_i, b_i) \times [c_i, d_i) \times [e_i, f_i)$, with $0 \le a_i, b_i, c_i, d_i, e_i, f_i \le 7$ for $1 \le i \le 23$, in such a way that the pattern is symmetrical under the transformation $(x, y, z) \to g\bar{x}$. In other words, $[a, b) \times [c, d) \times [e, f)$ is one of the subcuboids, so is $[7 - d, 7 - c) \times [7 - f, 7 - e) \times [7 - b, 7 - a)$.

Verified: no
Solve time: 1m23s

Solution

The construction cannot be recovered from the information supplied in the exercise statement alone. The required data are the coordinates of the $23$ subcuboids in Scott Kim's $7\times7\times7$ motley cube, and those data are encoded only in the omitted figure.

The proof requested by the exercise is not a deduction from the definition of a motley dissection. It requires reading the locations of the visible blocks in the picture, assigning coordinates to their faces, and then listing the corresponding intervals

$$ [a_i,b_i)\times[c_i,d_i)\times[e_i,f_i) $$

for $1\leq i\leq23$.

After those $23$ triples of intervals are obtained, the verification has two parts. First, each interval must satisfy

$$ 0\leq a_i,b_i,c_i,d_i,e_i,f_i\leq7, $$

and the collection must fill the cube

$$ [0,7)\times[0,7)\times[0,7) $$

without overlapping interiors. Second, for every listed block

$$ [a,b)\times[c,d)\times[e,f), $$

the transformed block

$$ [7-d,7-c)\times[7-f,7-e)\times[7-b,7-a) $$

must also occur in the list. This proves the required symmetry under

$$ (x,y,z)\to(y,z,x) $$

combined with reflection in the three coordinates.

The supplied text does not include the figure needed to determine the $23$ coordinate triples, so a complete worked solution with the explicit intervals cannot be derived without that image. Please provide the figure from exercise 382, and the coordinate verification can then be completed.