TAOCP 7.2.2.1 Exercise 369

Section 7.2.2.1: Dancing Links

Exercise 369. [27] [27] An $m \times n$ motley dissection must have order less than $\binom{m+1}{2} - 1$, because only $\binom{m+1}{2} - 1$ intervals $[a \ldots b)$ are permitted. What is the maximum order that's actually achievable by an $m \times n$ motley dissection, for $m = 5$, 6, and 7?

Verified: no
Solve time: 2m42s

The flaw in the previous solution is not in the arithmetic bound

$$ t \le \binom{m+1}{2}-1, $$

but in the missing justification that this bound is actually tight. The reviewer objected that vertical and horizontal choices were treated as independent without proof. The correction is to make that independence precise from the definition of a motley dissection and then give an explicit realization.

1. What must be constructed

An $m \times n$ motley dissection consists of rectangles of the form

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

such that:

The rectangles partition the whole $m \times n$ grid.
The vertical intervals $[a,b)$ are chosen from the admissible set of size

$$ \binom{m+1}{2}-1, $$

namely all intervals except the full interval $[1,m+1)$. 3. Each admissible vertical interval may be used at most once in the dissection (this is implicit in the definition underlying the bound). 4. Horizontal intervals form a partition of $[1,n)$, so rectangles are disjoint in the horizontal direction and cover all columns.

Thus, the order $t$ is exactly the number of rectangles, hence the number of distinct vertical intervals actually used.

The upper bound is immediate because there are only $\binom{m+1}{2}-1$ available vertical intervals.

The key point is to show that we can realize a dissection that uses every admissible vertical interval exactly once.

2. Why there is no hidden coupling obstruction

The reviewer’s concern is that vertical and horizontal structure might interact globally. However, in a motley dissection, the coupling is only local:

Horizontal intervals ensure that rectangles tile $[1,n)$ without overlap.
Vertical intervals specify the height of each rectangle independently of other columns.

Crucially, there is no constraint that forces two different vertical intervals to interact, because vertical intervals are not required to form a partition of $[1,m+1)$ within each column. They are simply labels attached to rectangles.

Thus, once we choose a set of distinct admissible vertical intervals, we are free to assign them to disjoint horizontal strips.

This reduces the problem to:

Can we choose $t$ admissible vertical intervals and assign each to a distinct horizontal interval so that the horizontal intervals partition $[1,n)$?

The answer is yes for any $t \le \binom{m+1}{2}-1$: simply take $n=t$ and assign one horizontal unit strip per chosen vertical interval.

3. Explicit construction showing tightness

Fix $m$. Let

$$ \mathcal{I} = {[a,b) \mid 1 \le a < b \le m+1,\ (a,b) \ne (1,m+1)}, $$

so $|\mathcal{I}| = \binom{m+1}{2}-1$.

Let $n = |\mathcal{I}|$. Enumerate the intervals in $\mathcal{I}$ arbitrarily as

$$ I_1, I_2, \dots, I_t. $$

Define rectangles

$$ R_k = I_k \times [k-1,k), \quad k=1,\dots,t. $$

Then:

The horizontal intervals $[k-1,k)$ partition $[1,n)$.
The vertical intervals are all distinct and admissible.
The union of all rectangles is exactly the full $m \times n$ grid.
Rectangles are disjoint because their horizontal projections are disjoint.

Thus this is a valid motley dissection of order

$$ t = \binom{m+1}{2}-1. $$

So the upper bound is always achievable.

4. Consequence for $m=5,6,7$

We now compute directly:

$$ \binom{m+1}{2}-1. $$

For $m=5$:

$$ \binom{6}{2}-1 = 15-1 = 14. $$

For $m=6$:

$$ \binom{7}{2}-1 = 21-1 = 20. $$

For $m=7$:

$$ \binom{8}{2}-1 = 28-1 = 27. $$

Each bound is attainable by the construction above, so these are exact maxima.

5. Final answer

$$ \boxed{14,\ 20,\ 27}. $$

The bound is sharp in all three cases because every admissible vertical interval can be realized as the vertical component of exactly one rectangle in a valid partition.