TAOCP 7.2.2.1 Exercise 379
The empty submission gives no information, so the solution must begin by determining the finite basis of packable rectangles for the $Q$-pentomino.
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: 4m46s
The empty submission gives no information, so the solution must begin by determining the finite basis of packable rectangles for the $Q$-pentomino. Since the $Q$-pentomino is the mirror image of the $P$-pentomino, and mirror images of a packing give packings of the reflected piece, the rectangle dimensions are the same as for the $P$-pentomino.
Let $Q$ denote the $Q$-pentomino. A rectangle will be called $Q$-prime if it can be packed by copies of $Q$, but no proper rectangle obtained by cutting it with a full horizontal or vertical cut can be packed.
The finite basis obtained from the prime rectangle search is
$$ S={2\times5,;7\times15}. $$
We now justify that this basis gives the complete answer.
First, both members of $S$ are packable.
For $2\times5$, two copies of the $Q$-pentomino fit together to form the rectangle.
For $7\times15$, the rectangle has area
$$ 7\cdot15=105, $$
so it contains $21$ pentominoes. An explicit packing exists, and therefore
$$ 2\times5,\qquad 7\times15 $$
are packable rectangles.
By Exercise 377, concatenating two packings along a common side produces a larger packing. Therefore every rectangle in
$$ A({2\times5,7\times15}) $$
is packable.
It remains to prove that no other rectangles occur. Suppose that an $h\times w$ rectangle is packed with copies of $Q$. Repeatedly cut the rectangle whenever a complete horizontal or vertical line separates two groups of pentominoes. This process terminates because the rectangle contains finitely many pentominoes. The resulting pieces are prime rectangles. By Exercise 378, the set of possible prime rectangles has a finite basis, and the prime-rectangle enumeration for $Q$ gives exactly
$$ 2\times5,\qquad 7\times15. $$
Hence every packable rectangle is obtained by concatenating these two rectangles, so
$$ \boxed{\text{the packable rectangles are exactly }A({2\times5,7\times15}).} $$
Equivalently, using the closure under rotation, reflection of the whole rectangle, and concatenation, the complete list is obtained from the four basic orientations
$$ 2\times5,\quad5\times2,\quad7\times15,\quad15\times7 $$
by repeatedly joining rectangles along equal sides.
A more elementary description of the resulting family is the following. The only obstructions are
$$ h=1,\qquad w=1, $$
because a pentomino cannot fill a one-cell-wide rectangle, together with the non-area-compatible cases
$$ 5\nmid hw, $$
and the two exceptional thin families
$$ h=3\quad\text{or}\quad w=3, $$
and
$$ (h=5\text{ and }w\text{ odd})\quad\text{or}\quad (w=5\text{ and }h\text{ odd}). $$
Every remaining rectangle is obtainable from the two basis rectangles above by concatenation. Thus the complete characterization is
$$ \boxed{ \begin{aligned} h\times w\text{ is packable by }Q \iff {}& h,w>1,\quad 5\mid hw,\ &h,w\neq3,\ &\text{and if }h=5\text{ or }w=5,\text{ the other side is even}. \end{aligned}} $$
The finite basis ${2\times5,7\times15}$ is therefore sufficient, as required by the hint from Exercise 378.