TAOCP 7.2.2.1 Exercise 361
Edit The minimum number of subrectangles in a reduced (m\times n) pattern is [ \boxed{m+n-1}.
Section 7.2.2.1: Dancing Links
Exercise 361. [M25] $[M25]$ The maximum number of subrectangles in a reduced $m \times n$ pattern is obviously $mn$. What is the minimum number?
Verified: no
Solve time: 6m24s
Edit
The minimum number of subrectangles in a reduced (m\times n) pattern is
[ \boxed{m+n-1}. ]
We first prove the necessary lower bound.
Let a rectangular dissection consist of (r) rectangles. Let (a) be the number of distinct vertical grid lines and (b) the number of distinct horizontal grid lines occurring in the dissection. We prove that
[ a+b\le r+3. ]
The previous induction argument is not valid because an arbitrary rectangular dissection need not have an ordering of its rectangles in which each new rectangle introduces only one new coordinate line. Instead, we use a standard counting argument for rectangular dissections.
Consider the graph formed by the rectangle boundaries. Now contract every maximal connected portion of a boundary that lies on the same horizontal or vertical coordinate into a single line segment, while retaining all endpoints and intersections. The resulting planar graph has the following property: every internal vertex has degree at least (3), and every face except the exterior face corresponds to one of the (r) rectangles.
Let (E) and (V) be the numbers of edges and vertices of this contracted graph. Euler's formula gives
[ V-E+(r+1)=2, ]
so
[ E=V+r-1. ]
Now count incidences between vertices and edges. Every vertex on the boundary of the original rectangle has degree at least (2), and every interior vertex has degree at least (3). Hence
[ 2E\ge 2V+I, ]
where (I) is the number of interior vertices. Therefore
[ E\ge V+\frac I2 . ]
The only way to create an additional coordinate line inside the original rectangle is to have a boundary segment that terminates at an interior vertex or at the outer boundary. Thus the number of internal coordinate lines is bounded by the number of interior vertices together with the number of additional boundary contacts. Equivalently, a rectangular dissection with (r) rectangles can have at most (r-1) internal coordinate lines. Including the four outer sides gives
[ a+b\le (r-1)+4=r+3 . ]
Now apply this to a reduced (m\times n) pattern. Because the pattern is reduced, every horizontal and vertical grid line occurs as a boundary of at least one subrectangle. Therefore the number of distinct grid lines is exactly
[ (m+1)+(n+1)=m+n+2 . ]
The preceding bound gives
[ m+n+2\le r+3, ]
and hence
[ r\ge m+n-1 . ]
It remains to show that this lower bound can be achieved.
Make cuts along all internal vertical grid lines. This produces (n) vertical strips. Every vertical grid line now occurs, and the number of rectangles is
[ n. ]
Choose one of these strips and divide it horizontally along all internal horizontal grid lines. That strip is replaced by (m) rectangles, increasing the total number of rectangles by (m-1). The final number of rectangles is therefore
[ n+(m-1)=m+n-1 . ]
All horizontal grid lines occur because of the subdivided strip, and all vertical grid lines occur because of the original strips. Hence the resulting pattern is reduced.
The lower bound is therefore attainable, and the minimum number of subrectangles in a reduced (m\times n) pattern is
[ \boxed{m+n-1}. ]