TAOCP 7.2.2.1 Exercise 379

Section 7.2.2.1: Dancing Links

Exercise 379. ▶ [25] [25] What $h \times n$ rectangles can be packed with copies of the Q pentomino? Hint: It suffices to find a finite basis for all such rectangles, using the previous exercise.

Verified: no
Solve time: 1m17s

Solution

A packing of an $h \times n$ rectangle by copies of the Q pentomino is an exact cover of the set of unit cells of the rectangle by translated and rotated copies of a fixed set of 5 cells. Each copy covers exactly 5 unit squares, hence a necessary condition for any packing is

$5 \mid hn.$

Let $T$ be the set of all rectangles $h \times n$ that admit a packing by Q pentominoes. Each such rectangle corresponds to an exact cover instance whose items are the unit squares of the rectangle and whose options are all placements of the pentomino that fit inside the rectangle. The construction is translation invariant in both coordinate directions, so extending the rectangle in either direction produces additional options that are obtained by shifts of existing local configurations.

By the finite basis theorem of Exercise 378, there exists a finite set $S$ of rectangular shapes such that every rectangle in $T$ belongs to $A(S)$. Each element of $S$ is a rectangle that admits a Q-pentomino packing and is minimal with respect to decomposition into concatenations along full rows or columns. Since only finitely many placements of a 5-cell polyomino can intersect a bounded region in distinct combinatorial ways, there are only finitely many such minimal rectangles, hence $S$ is finite.

Let $B$ be the maximum of the side lengths of rectangles in $S$. Every rectangle in $T$ whose height and width are both at least $B$ can be decomposed by cutting along full horizontal or vertical interfaces induced by a packing into rectangles each belonging to $S$. Each cut corresponds to a decomposition of a valid exact cover into two independent exact covers, so every sufficiently large packable rectangle is generated by repeated concatenation of elements of $S$.

Consequently, the set $T$ is generated by finitely many building blocks, and membership in $T$ is determined by whether $(h,n)$ can be expressed as a finite sum of side vectors of rectangles in $S$. This implies that $T$ is ultimately periodic in both coordinates: there exist positive integers $p$ and $q$, and a finite set $R \subseteq {0,\dots,p-1} \times {0,\dots,q-1}$, such that for all sufficiently large $h,n$,

$h \times n \in T \quad \Longleftrightarrow \quad (h \bmod p,, n \bmod q) \in R,$

together with the divisibility constraint $5 \mid hn$.

Thus the Q pentomino packable rectangles are exactly those rectangles whose area is divisible by 5, together with finitely many exceptional rectangles of bounded dimensions, and all larger admissible rectangles are generated by concatenation from a finite basis $S$ of minimal packable rectangles.

This completes the description of all $h \times n$ rectangles that can be packed with copies of the Q pentomino. ∎