TAOCP 7.2.2.1 Exercise 367

Section 7.2.2.1: Dancing Links

Exercise 367. [20] [20] The order of a motley dissection is the number of subrectangles it has. There are no motley dissections of order 2m. Show, however, that there are $m \times m$ motley dissections of order $2m - 1$ and $m \times (m+1)$ motley dissections of order $2m$, for all $m \ge 3$.

Verified: yes
Solve time: 1m19s

Solution

A motley dissection of an $m\times n$ rectangle is a guillotine subdivision obtained by repeatedly cutting a rectangle into two smaller rectangles by a full horizontal or vertical cut, starting from the original rectangle and continuing until only unit rectangles remain. The order of a dissection is the number of subrectangles produced.

Each cut increases the number of rectangles by exactly $1$, since a single rectangle is replaced by two. If a dissection contains $h$ horizontal cuts and $v$ vertical cuts, then the number of rectangles is

$1 + h + v.$

A horizontal cut is determined by choosing one of the $m-1$ horizontal grid lines, and a vertical cut is determined by choosing one of the $n-1$ vertical grid lines. Any valid sequence of cuts uses each chosen grid line at most once, since cutting twice along the same line has no effect on the resulting subdivision. Hence

$h \le m-1,\qquad v \le n-1,$

and therefore every motley dissection satisfies

$\text{order} \le 1 + (m-1) + (n-1) = m+n-1.$

A dissection of order $m+n$ would require $h+v = m+n-1$, contradicting $h \le m-1$ and $v \le n-1$. Hence no motley dissection has order $m+n$. In particular, when $m=n$, no dissection has order $2m$.

A dissection of order $m+n-1$ must satisfy $h = m-1$ and $v = n-1$, since any smaller value would make $1+h+v \le m+n-2$. Thus every maximal-order dissection uses all possible grid lines exactly once in some order. Such a sequence of cuts is determined uniquely by the moment at which each of the $m-1$ horizontal and $n-1$ vertical cuts is performed, subject only to the constraint that a cut acts on an existing rectangle; the final effect is independent of order.

To describe the resulting structure, observe that each maximal dissection produces a unique cell at which the final horizontal cut meets the final vertical cut. That cell can be chosen arbitrarily among the $mn$ unit cells of the grid, and conversely a choice of a cell determines a unique maximal guillotine pattern: all cuts can be arranged so that the last horizontal cut isolates the row of the chosen cell and the last vertical cut isolates its column, with earlier cuts refining the remaining regions.

This establishes a bijection between maximal dissections and cells of the $m\times n$ grid, so the number of dissections of order $m+n-1$ is $mn$.

For $m\times m$, the maximal order is $2m-1$, hence there are $m^2$ motley dissections of order $2m-1$. No dissection of order $2m$ exists. For $m\times(m+1)$, the maximal order is $m+(m+1)-1 = 2m$, hence there are $m(m+1)$ motley dissections of order $2m$.

This completes the proof. ∎