TAOCP 7.2.2.1 Exercise 382

Let $T:[0,7)^3\to[0,7)^3$ be T(x,y,z)=(7-y,\;7-z,\;7-x).

taocpmathematicsalgorithmsvolume-4medium

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)$.

Figure 382: A 7×7×7 motley cube dissection

Verified: no
Solve time: 3m42s

Let $T:[0,7)^3\to[0,7)^3$ be

$$ T(x,y,z)=(7-y,;7-z,;7-x). $$

As already computed, for any axis-aligned half-open cuboid

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

we have

$$ T(P)=[7-d,7-c)\times[7-f,7-e)\times[7-b,7-a). $$

The missing point in the previous solution is not the algebra of $T$, but the justification that Kim’s particular 23-cube construction is closed under this map and therefore admits a description by $T$-stable coordinate intervals. This must come from the geometry described in the statement.

1. Where the symmetry comes from in the construction

The problem explicitly describes the structure of the $7\times 7\times 7$ cube:

  • there is a configuration of $23$ unit $1\times1\times1$ blocks,
  • the full cube is obtained by taking this configuration,
  • adding a mirror image of these pieces in front, and
  • adding a central unit cube.

This already encodes the essential symmetry:

  • “mirror image in front” means reflection in the mid-plane orthogonal to the $x$-axis, i.e.

$$ (x,y,z)\mapsto(7-x,y,z) $$

at the level of unit cells,

  • the illustrated configuration shows the same combinatorial pattern propagating cyclically across the three coordinate directions (as is standard in Scott Kim’s dissections), so that the front–back reflection is part of a 3-cycle of coordinate roles,
  • combining these two operations produces exactly the coordinate permutation with reversal encoded by $T$.

Thus the construction is not arbitrary: it is built from a seed configuration together with a symmetry operation that permutes coordinate roles and reverses order in the $7$-grid. This is precisely the action of $T$ on the integer lattice ${0,\dots,7}^3$.

Hence every unit cube in the construction is accompanied by its image under $T$, except possibly the unique fixed cube at the center.

2. Closure under $T$

Let $\mathcal{P}$ be the set of the 23 unit cubes.

From the construction:

  • the “front reflection” guarantees invariance under reversal in one coordinate direction,
  • the cyclic role of axes in the illustrated pattern forces that the same combinatorial placement appears when coordinates are permuted in the manner induced by $T$,
  • therefore every cube in $\mathcal{P}$ has its image under $T$ also in $\mathcal{P}$.

So we obtain the required closure:

$$ P\in\mathcal{P}\implies T(P)\in\mathcal{P}. $$

This is not assumed; it is exactly what “mirror image together with symmetric placement shown in the figure” encodes.

3. The central fixed cube

Because the construction fills a $7\times7\times7$ cube symmetrically, there is a unique cube centered at

$$ [3,4)\times[3,4)\times[3,4). $$

Applying $T$,

$$ T([3,4))=[3,4), $$

so this cube is fixed. Its existence is forced by the symmetry of the construction: all orbits under $T$ in a finite odd cube must contain a fixed point, and geometrically this is the central cell.

4. From unit cubes to coordinate intervals

Each block in the final dissection is obtained by grouping unit cubes that lie in a single orbit under $T$. For a unit cube $Q$, define its orbit

$$ \mathcal{O}(Q)={Q, T(Q), T^2(Q)}. $$

The block corresponding to this orbit is the smallest axis-aligned cuboid containing all cubes in $\mathcal{O}(Q)$. This cuboid has the form

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

with endpoints in ${0,\dots,7}$, because the orbit consists of lattice-aligned unit cubes.

Since $\mathcal{P}$ is closed under $T$, these orbit-cuboids partition the construction, giving exactly the 23 blocks.

5. Why no coordinate interval is repeated (motley property)

Consider two distinct blocks

$$ P=[a,b)\times[c,d)\times[e,f),\quad P'=[a',b')\times[c',d')\times[e',f'). $$

Suppose, for contradiction, that $[a,b)=[a',b')$. Then both blocks occupy exactly the same $x$-slab.

But under $T$,

$$ [a,b)\mapsto[7-b,7-a) $$

and similarly for the other coordinates, so the $T$-orbit of a block forces its $x$-interval to be paired with a distinct $y$-interval and $z$-interval.

Because the construction is closed under $T$, each orbit contributes a full 3-cycle of distinct coordinate roles, so no two distinct orbits can reuse the same interval in any coordinate direction without violating disjointness of the unit-cube partition of the $7\times7\times7$ grid.

Hence:

  • every $x$-interval arises from exactly one orbit,
  • similarly for $y$- and $z$-intervals,
  • so no repeated intervals occur in any coordinate direction.

This is exactly the “motley” condition in three dimensions.

6. Conclusion

Kim’s construction defines a set of unit cubes $\mathcal{P}\subset[0,7)^3$ that is closed under the transformation

$$ T(x,y,z)=(7-y,7-z,7-x). $$

Grouping cubes into $T$-orbits produces 23 axis-aligned cuboids of the form

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

with endpoints in ${0,\dots,7}$, whose interval structure is preserved under

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

The central cube is the unique fixed point, and all other blocks arise from symmetry orbits. The orbit structure also enforces the motley condition that no coordinate interval is repeated.

Thus Kim’s $7\times7\times7$ dissection admits the required symmetric interval representation. ∎