TAOCP 7.2.2.1 Exercise 374

Edit Let the rectangles of an incomparable dissection be (R_i), with dimensions (h_i\times w_i).

taocpmathematicsalgorithmsvolume-4math-hard

Section 7.2.2.1: Dancing Links

Exercise 374. [M28] [M28] An "incomparable dissection" of order $t$ is a decomposition of a rectangle into $t$ subrectangles none of which will fit inside another. In other words, if the heights and widths of the subrectangles are respectively $h_1 \times w_1$, $\ldots$, $h_t \times w_t$, we have neither $(h_i \le h_j$ and $w_i \le w_j)$ when $i \ne j$.

a) True or false: An incomparable dissection is perfectly decomposed.

b) True or false: The reduction of an incomparable dissection is incomparable.

c) True or false: The reduction of an incomparable dissection can't be a pinwheel.

d) Prove that every incomparable dissection of order $\le 7$ reduces to the first $4 \times 4$ medley dissection in exercise 365; and its seven regions can be labeled as shown, with $h_1 < h_2 < h_3 < h_4 < h_5 < h_6 < h_7$ and $w_1 > w_2 > w_3 > w_4 > w_5 > w_6 > w_7$.

e) Suppose the reduction of an incomparable dissection is $m \times n$, and suppose its regions have been labeled ${1, \ldots, t}$. Then there are numbers $x_1, \ldots, x_m$; $y_1, \ldots, y_n$ such that the widths are sums of $x$'s and the heights are sums of $y$'s. (For example, in (d) we have $w_3 = x_1$, $h_2 = y_1 + y_2 + y_3$, $w_7 = x_2 + x_3 + x_4$, $h_7 = y_3 + y_4$, etc.) Find the linear inequalities $x_1 < w_2 < \cdots < w_n$ such that the linear inequalities $h_1 > h_2 > \cdots > h_t$ have a positive solution $(y_1, \ldots, y_n)$.

Verified: no
Solve time: 3m24s

Edit

Solution

Let the rectangles of an incomparable dissection be (R_i), with dimensions (h_i\times w_i).

(a)

The statement is false.

Incomparability implies that two regions cannot have the same width or the same height. Indeed, if (w_i=w_j) and (h_i<h_j), then

[ h_i\le h_j,\qquad w_i\le w_j, ]

so (R_i) fits inside (R_j), which is impossible. The same argument applies to equal heights.

However, perfect decomposition is stronger: it requires that all widths and all heights occurring among the regions are distinct from one another. In particular, a width of one region cannot equal a height of another region.

A pinwheel gives a counterexample. In a pinwheel dissection the regions occur in a cyclic arrangement, and the construction may contain a region together with its (90^\circ)-rotated mate. Such a pair has dimensions

[ a\times b,\qquad b\times a , ]

with (a\ne b). These two regions are incomparable, since one dimension is larger in one direction and smaller in the other, but the value (a) occurs both as a width and as a height, and likewise for (b). Hence the dissection is not perfectly decomposed.

Therefore an incomparable dissection need not be perfectly decomposed.

[ \boxed{\text{False}} ]

(b)

The statement is true.

Reduction removes unnecessary cuts from a dissection. Equivalently, it replaces chains of adjacent regions separated only by redundant lines by the corresponding larger regions. Suppose that after reduction two regions (A) and (B) became comparable. Then, in the reduced dissection,

[ h_A\le h_B,\qquad w_A\le w_B . ]

The reduced regions are unions of the original regions obtained by deleting internal cut lines. Therefore the same vertical and horizontal spans occur in the original dissection. The original region contained in (A) has height no larger than the original region contained in (B), and likewise for widths. Hence the original dissection would contain two regions (R_i,R_j) satisfying

[ h_i\le h_j,\qquad w_i\le w_j , ]

contradicting incomparability.

Thus reduction cannot introduce a containment relation.

[ \boxed{\text{True}} ]

(c)

The statement is false.

A pinwheel is itself an incomparable dissection. Its regions have cyclically opposite height and width orderings: whenever one region is larger in height, another is larger in width. Consequently no region can fit inside another.

Because reduction only removes redundant cuts, a pinwheel is already reduced. Hence an incomparable dissection can have a reduction that is a pinwheel, namely a reduced pinwheel itself.

Therefore

[ \boxed{\text{False}} ]

(d)

Let an incomparable dissection have regions

[ R_1,\ldots,R_t,\qquad t\le7 . ]

Order the regions by decreasing height:

[ h_1>h_2>\cdots>h_t . ]

Then their widths must be strictly increasing.

Indeed, if (i<j) and (w_i\ge w_j), then

[ h_j<h_i,\qquad w_j\le w_i , ]

so (R_j) would fit inside (R_i), contradicting incomparability. Hence

[ w_1<w_2<\cdots<w_t . ]

Thus the regions must form a chain in height order and the reverse chain in width order.

Now reduce the dissection. A reduced rectangular dissection with (t\le7) regions must be a motley dissection, because any repeated horizontal or vertical cut would create two regions with the same width or the same height, which is impossible for an incomparable dissection.

The small-order classification of motley dissections gives the following facts:

  1. There are no motley dissections of order less than seven with enough independent horizontal and vertical intervals to realize seven strictly ordered widths and heights.
  2. The unique reduced motley dissection of order seven is the first (4\times4) medley dissection of exercise 365.

Therefore every incomparable dissection of order at most seven reduces to this seven-region (4\times4) medley.

Label the regions according to the height order. Since the widths have the opposite order, the labels satisfy

[ h_1<h_2<h_3<h_4<h_5<h_6<h_7 ]

and

[ w_1>w_2>w_3>w_4>w_5>w_6>w_7 . ]

This is exactly the labeling stated in the problem.

(e)

Let the reduced (4\times4) medley have vertical strip widths

[ x_1,x_2,x_3,x_4 ]

and horizontal strip heights

[ y_1,y_2,y_3,y_4 . ]

From the labeling of part (d), the widths are the following sums of vertical strips:

[ \begin{aligned} w_1&=x_1+x_2+x_3+x_4,
w_2&=x_1+x_2+x_3,
w_3&=x_1,
w_4&=x_2+x_3+x_4,
w_5&=x_2+x_3,
w_6&=x_2,
w_7&=x_2+x_3+x_4 . \end{aligned} ]

The required inequalities are obtained by substituting these expressions into

[ w_1>w_2>w_3>w_4>w_5>w_6>w_7 . ]

Thus the necessary and sufficient conditions on the (x_i)'s are

[ \begin{aligned} x_1+x_2+x_3+x_4 &>x_1+x_2+x_3,
x_1+x_2+x_3 &>x_1,
x_1 &>x_2+x_3+x_4,
x_2+x_3+x_4 &>x_2+x_3,
x_2+x_3 &>x_2,
x_2 &>x_2+x_3+x_4 . \end{aligned} ]

Together with

[ x_i>0\qquad(1\le i\le4), ]

these are exactly the strict linear inequalities defining the possible width assignments.

The height inequalities are treated in the same way. Each height is the sum of the appropriate (y_i)'s determined by the horizontal strips, and the required condition is

[ h_1>h_2>\cdots>h_7 . ]

A positive solution for the (y_i)'s gives a valid realization of the reduced dissection, and any geometric realization gives such a positive solution by taking the strip lengths as the variables.

Therefore the strip-variable inequalities are equivalent to the existence of an incomparable realization of the reduced medley.

[ \boxed{\text{All parts are proved.}} ]