TAOCP 7.2.2.1 Exercise 364

Section 7.2.2.1: Dancing Links

Exercise 364. [23] True or false: Every faultfree packing of an $m\times n$ rectangle by $1\times 3$ trominoes is reduced, except in the trivial cases $(m, n) = (1, 3)$ or $(3, 1)$.

Verified: no
Solve time: 12m13s

Solution

True.

We first recall the relevant definitions from the exercises and the section context.

• A rectangle decomposition (or pattern) of an (m \times n) rectangle is a partition of the rectangle into subrectangles whose interiors are disjoint and whose union is the whole rectangle.
• A pattern is faultfree if it cannot be split into two or more rectangles by a straight line (a fault line) that runs from one side of the big rectangle to the opposite side without crossing the interior of any subrectangle.
• A pattern is strictly reduced if no subrectangle ([a..b)\times[c..d)) satisfies ((a,b)=(0,m)) or ((c,d)=(0,n)); i.e., no piece spans the full height or the full width of the rectangle.
• A pattern is reduced if it belongs to the class of patterns produced by the construction of exercise 360; in particular, every strictly reduced pattern is reduced (exercise 362).

Now consider a faultfree packing of an (m \times n) rectangle by (1 \times 3) trominoes. Each tromino is either horizontal ((1 \times 3)) or vertical ((3 \times 1)). Suppose the packing contains a tromino that spans the full width of the rectangle. Then that tromino must be horizontal and we have (n = 3). Its top and bottom edges are horizontal segments that run from (x=0) to (x=3). These edges separate the tromino from the pieces above and below. Because the tromino spans the full width, the region above it (if any) and the region below it (if any) are themselves rectangles. The horizontal line along such an edge therefore cuts the big rectangle into two rectangles (the tromino and the rest), contradicting the assumption that the packing is faultfree. The same argument applies to a vertical tromino spanning the full height (which would force (m = 3)). Consequently, a faultfree tromino packing with (m,n > 1) cannot contain any tromino that spans the full width or the full height; i.e., it is strictly reduced.

By exercise 362, every strictly reduced pattern is reduced. Hence every faultfree tromino packing with ((m,n) \neq (1,3),(3,1)) is reduced.

The trivial cases ((1,3)) and ((3,1)) consist of a single tromino that necessarily spans the whole rectangle. They are faultfree (there is no way to split a single rectangle into two or more rectangles) but they are not strictly reduced, and the statement explicitly excludes them.

Therefore the statement is true. ∎

\boxed{\text{True}}