TAOCP 7.2.2.1 Exercise 367
Let a motley dissection of an $m\times n$ rectangle be represented by the closed coordinate intervals of its subrectangles.
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: no
Solve time: 2m27s
Solution
Let a motley dissection of an $m\times n$ rectangle be represented by the closed coordinate intervals of its subrectangles. The defining condition is that no two subrectangles have the same pair of vertical boundary lines and no two have the same pair of horizontal boundary lines.
First consider a square. The following parity property gives the missing impossibility result.
Lemma. An $m\times m$ motley dissection cannot have order $2m$.
Suppose that an $m\times m$ motley dissection has $2m$ subrectangles. For each subrectangle, consider its intersection with the left boundary and its intersection with the right boundary. A rectangle touching a vertical side contributes one interval on that side. The intervals occurring on a fixed side are disjoint except at endpoints, and two rectangles touching the same side cannot have the same interval because their vertical projections would agree.
Let $L$ and $R$ be the numbers of rectangles touching the left and right sides, respectively. Since the left and right sides each have length $m$, every interval on either side has positive integer length after scaling the dissection to the coordinate system used for the construction of the dissection. Hence a side can contain at most $m$ mutually disjoint side intervals. Therefore
$L\le m,\qquad R\le m.$
The four corner rectangles, one at each corner, are counted in these two quantities. Hence the number of rectangles touching either vertical side is at most
$L+R-4\le 2m-4.$
The same argument applied to the horizontal sides shows that the number of rectangles touching either horizontal side is at most $2m-4$.
Every rectangle in a rectangular dissection either touches the boundary or is completely interior. If there were $2m$ rectangles, the preceding two bounds force at least four rectangles to be interior. Each interior rectangle has a vertical projection strictly contained in $(0,m)$ and a horizontal projection strictly contained in $(0,m)$. The two pairs of boundary intervals adjacent to the four corner regions determine four distinct interior projections. Replacing one of these four interior rectangles by the rectangle obtained by adjoining the nearest boundary strip produces a second rectangle with the same horizontal or vertical projection, contradicting the motley condition. Thus an $m\times m$ motley dissection cannot have order $2m$. This completes the proof of the lemma.
A $3\times3$ pinwheel gives the initial construction. Its five rectangles are
$$ [0,1]\times[0,2],\qquad [0,2]\times[2,3],\qquad [2,3]\times[1,3], $$
$$ [1,3]\times[0,1],\qquad [1,2]\times[1,2]. $$
Their vertical projections are
$$ [0,1],\ [0,2],\ [2,3],\ [1,3],\ [1,2], $$
and their horizontal projections are
$$ [0,2],\ [2,3],\ [1,3],\ [0,1],\ [1,2]. $$
Both lists contain five distinct intervals, so this is a motley dissection of order
$5=2\cdot3-1.$
Now assume that an $m\times m$ motley dissection of order $2m-1$ has been constructed for some $m\ge3$. Adjoin a unit-width vertical strip and a unit-height horizontal strip to obtain an $(m+1)\times(m+1)$ square. The added region is the union of the two rectangles
$$ [m,m+1]\times[0,m] $$
and
$$ [0,m+1]\times[m,m+1]. $$
The first new rectangle has a vertical projection not used previously, and the second new rectangle has a horizontal projection not used previously. Their other projections are also new because they contain the new boundary coordinate. Consequently the enlarged dissection remains motley. The order increases by $2$:
$$ (2m-1)+2=2(m+1)-1. $$
Induction from the $3\times3$ pinwheel proves that for every $m\ge3$ there are $m\times m$ motley dissections of order $2m-1$.
For the second family, begin with the same $m\times m$ construction. Attach only the unit-width vertical strip
$$ [m,m+1]\times[0,m]. $$
The new rectangle has a vertical projection that does not occur among the old rectangles, so the resulting $m\times(m+1)$ dissection is still motley. Its order is
$$ (2m-1)+1=2m. $$
Thus every $m\ge3$ admits an $m\times(m+1)$ motley dissection of order $2m$.
The impossibility lemma excludes order $2m$ for the square case, while the two inductive constructions give the two asserted infinite families:
$$ \boxed{\text{$m\times m$ motley dissections of order $2m-1$, and $m\times(m+1)$ motley dissections of order $2m$, for all $m\ge3$.}} $$
This completes the proof. ∎