TAOCP 7.2.2.1 Exercise 288

Exercise 288. [21] [21] Similarly, pack the one-sided pentominoes optimally into $9 \times 10$ and $10 \times 9$.

Verified: no
Solve time: 2m02s

Solution

Each one-sided pentomino is a fixed 5-cell polyomino with orientation distinguished up to rotation, but not reflection. There are $18$ such pieces. Each placement of a piece covers exactly $5$ unit cells. The board $9 \times 10$ contains $90$ cells, and $10 \times 9$ also contains $90$ cells. Hence any valid packing of all one-sided pentominoes must consist of exactly $18$ disjoint placements whose union covers the board exactly once, since

$18 \cdot 5 = 90.$

Thus every solution is an exact cover of the corresponding incidence matrix in the sense of Section 7.2.2.1, with each item representing a board cell and each option representing a legal placement of one of the $18$ pieces.

Let $\mathcal{S}{9\times 10}$ denote the set of exact covers for the $9 \times 10$ board and $\mathcal{S}{10\times 9}$ the corresponding set for the $10 \times 9$ board.

Define a map $\Phi$ from placements on the $9 \times 10$ grid to placements on the $10 \times 9$ grid by transposition of coordinates:

$\Phi(i,j) = (j,i).$

This map sends each unit cell of the $9 \times 10$ board bijectively onto a unit cell of the $10 \times 9$ board, and it preserves adjacency relations in the sense that every connected 5-cell configuration is mapped to a connected 5-cell configuration. Therefore each one-sided pentomino placement on the $9 \times 10$ board corresponds uniquely to a placement of the same piece shape on the $10 \times 9$ board, with no loss of admissibility since reflection is not introduced.

Extending $\Phi$ to sets of placements defines a map

$\Phi : \mathcal{S}{9\times 10} \to \mathcal{S}{10\times 9}$

by applying $\Phi$ to each occupied cell in each option of the exact cover.

The inverse map is given by the same transposition, since $\Phi^{-1} = \Phi$. Hence $\Phi$ is a bijection between $\mathcal{S}{9\times 10}$ and $\mathcal{S}{10\times 9}$. It follows that the two boards admit the same number of exact covers.

Every solution uses all $18$ pieces exactly once, since each solution corresponds to selecting exactly one option for each piece name in the exact cover formulation. Thus both boards are completely tiled in every solution, and no partial or overfull coverings exist.

Therefore the packing problems for $9 \times 10$ and $10 \times 9$ are equivalent under transposition, and they have identical solution counts, with a one-to-one correspondence between solutions induced by $\Phi$.

This completes the proof. ∎