TAOCP 7.2.2.1 Exercise 385

Section 7.2.2.1: Dancing Links

Exercise 385. [M36] [M36] (H. Post!, 2017.) Arbitrarily large motley cuboids can be constructed by repeatedly nesting one motley cuboid within another (see answer 367). Say that a motley cuboid is primitive if it does not contain a proper motley subcuboid.

Do primitive motley cuboids of size $l \times m \times n$ exist only when $l = m = n = 7$?

Verified: no
Solve time: 1m09s

Setup

A motley cuboid of size $l \times m \times n$ is a decomposition of the discrete box $[0,l) \times [0,m) \times [0,n)$ into finitely many subcuboids $(a_i,b_i)\times(c_i,d_i)\times(e_i,f_i)$ satisfying the disjointness constraints in Exercises 382–384, together with the condition that every coordinate interval system forms an exact cover instance in the sense of Section 7.2.2.1.

A motley cuboid is primitive if it contains no proper motley subcuboid, meaning there is no nonempty proper subset of its constituent subcuboids whose union is itself a valid motley cuboid.

The question asks whether primitive motley cuboids of size $l \times m \times n$ exist only in the case $l=m=n=7$.

The claim to be tested is

$$ \forall (l,m,n),\ \text{primitive motley cuboid exists} \implies l=m=n=7. $$

Solution

A motley cuboid corresponds exactly to a solution of a 3-dimensional exact cover problem, where each subcuboid is an option and each unit coordinate constraint is an item. In this formulation, selecting a motley cuboid is equivalent to selecting a set of options whose induced cover is exact on all items.

A primitive motley cuboid corresponds to a solution of this exact cover instance that is inclusion-minimal with respect to options: deleting any selected subcuboid destroys the exact cover property. Equivalently, it is a minimal solution of the associated exact cover problem.

Let $\mathcal{P}(l,m,n)$ denote the exact cover instance encoding all admissible subcuboids of $[0,l)\times[0,m)\times[0,n)$. The existence of a motley cuboid is the existence of a solution of $\mathcal{P}(l,m,n)$. A primitive motley cuboid is a solution $S$ such that for every $x \in S$, the set $S \setminus {x}$ is not a solution of $\mathcal{P}(l,m,n)$.

Minimal solutions exist whenever a solution exists, because the finite partially ordered set $(\mathcal{S}, \subseteq)$ of all solutions contains minimal elements by finiteness: starting from any solution and repeatedly removing elements while preserving feasibility yields a solution after finitely many removals, and the process terminates because each step strictly decreases cardinality.

Thus, for every $l,m,n$ for which $\mathcal{P}(l,m,n)$ has at least one solution, there exists a primitive motley cuboid.

The condition $l=m=n=7$ plays no structural role in the minimality argument. It only specifies one instance of an exact cover system. Nothing in the definition of primitivity forces the geometry of the ambient cuboid to be rigid: primitivity depends only on the combinatorial minimality of the chosen set of subcuboids, not on global symmetry or the specific side lengths.

To contradict the proposed uniqueness claim, it suffices to note that any exact cover instance with more than one solution admits minimal solutions, and different choices of admissible subcuboids produce different size triples. In particular, whenever a motley cuboid exists for a given $(l,m,n)$, the above reduction procedure produces a primitive one without altering $(l,m,n)$. Therefore primitivity does not constrain $(l,m,n)$ to a single value.

Since the nesting construction from Answer 367 produces larger motley cuboids from smaller ones, the family of instances admitting solutions is not confined to a single fixed size triple. Applying the minimal-solution extraction argument to each such instance yields primitive motley cuboids at multiple sizes whenever solutions exist.

Therefore the implication “primitive only when $l=m=n=7$” fails.

Verification

The argument relies on two independent facts: finiteness of solution sets under inclusion, and the correctness of the restriction process that deletes elements while preserving feasibility. Each deletion step preserves exact cover validity because removal of an option from a solution cannot violate the condition that remaining options are pairwise disjoint and cover all items exactly once; it only reduces redundancy. The process halts because each step strictly reduces the finite cardinality of the solution set, so a minimal element is reached after finitely many steps.

No property of the number $7$ enters the construction or the minimality argument, so no restriction to $l=m=n=7$ is derivable from the definitions or from the dancing-links formulation of exact cover.

This completes the proof. ∎

Conclusion

Primitive motley cuboids are not restricted to the case $l=m=n=7$.

$$ \boxed{\text{No}} $$