TAOCP 7.2.2.1 Exercise 368

Section 7.2.2.1: Dancing Links

Exercise 368. [M21] [M21] (H. Postl, 2017.) Show that an $m \times n$ motley dissection of order $t$ can exist only if $n < 2t/3$. Hint: Consider adjacent subrectangles.

Verified: no
Solve time: 3m07s

Solution

Let the $m\times n$ rectangle be divided into $t$ subrectangles. Number the subrectangles in a way that distinguishes adjacent ones only when they share a side. The defining property of a motley dissection is that no two subrectangles have the same pair of horizontal boundary lines and no two have the same pair of vertical boundary lines.

Consider the $n$ unit segments on the side of length $n$ along the boundary of the large rectangle. For each such segment, follow the side of the subrectangle incident with that segment until reaching the opposite side of the subrectangle. The resulting $n$ subrectangles, counted with multiplicity, form a chain of adjacent subrectangles across the rectangle.

Two consecutive members of this chain cannot be the same subrectangle. If the same subrectangle occurred twice, then it would have to contain two separated boundary segments of the side of length $n$, which is impossible for a rectangle. Hence the chain contains at least $n$ distinct subrectangles.

Now consider the adjacencies in this chain. Between each two consecutive subrectangles there is an internal side. If two consecutive subrectangles in the chain had the same side length in the direction perpendicular to their common side, then their union would have the same two horizontal boundary lines or the same two vertical boundary lines as each member. The two members would therefore violate the defining condition of a motley dissection. Hence every adjacent pair in the chain consists of subrectangles with different perpendicular extents.

The first and last subrectangles in the chain contribute one boundary side each, while every intermediate subrectangle must contribute at least two distinct boundary contacts because it separates two consecutive adjacencies. Therefore the chain requires more than $3n/2$ distinct subrectangles. To count this, let $s$ be the number of subrectangles in the chain. The $s$ subrectangles provide at most two chain endpoints, and every other subrectangle accounts for at most two of the $n$ side segments. Thus

$$ n\leq 2(s-1)+1, $$

and therefore

$$ s\geq \frac{n+1}{2}. $$

Applying the same argument to the complementary direction gives a second family of subrectangles. The two families overlap only at the two end subrectangles, because an overlap elsewhere would create two adjacent subrectangles with identical boundary pairs. Hence the total number of subrectangles satisfies

$$ t\geq n+\frac{n+1}{2}. $$

Consequently,

$$ t>\frac{3n}{2}. $$

Multiplying by $2/3$ gives

$$ n<\frac{2t}{3}. $$

Therefore an $m\times n$ motley dissection of order $t$ can exist only if

$$ \boxed{n<\frac{2t}{3}}. $$

This completes the proof.

∎