TAOCP 7.2.2.1 Exercise 273

Section 7.2.2.1: Dancing Links

Exercise 273. [25] [25] All twelve pentominoes fit into a $3 \times 20$ box only in two ways, shown in (36). a) How many ways are there to fit eleven of them into that box? b) In how many solutions to (a) are the five holes nonadjacent, kingwise? c) In how many ways can eleven pentominoes be packed into a $3 \times 19$ box?

Verified: no
Solve time: 2m29s

Solution

Let the $3\times 20$ board be fixed. By the statement, all full coverings by the twelve pentominoes occur in exactly two configurations, denoted in (36). Each such configuration is a partition of the board into twelve disjoint 5-cell regions.

(a)

Removing one pentomino from a complete tiling produces a placement of the remaining eleven pentominoes covering exactly $55$ cells of the board, leaving a 5-cell uncovered region equal to the cells occupied by the removed pentomino in that tiling.

Fix one of the two full tilings. There are twelve pentominoes in it, hence twelve distinct choices of a pentomino whose removal produces an 11-pentomino packing. Distinct pentominoes occupy disjoint sets of cells, so the resulting 11-coverings are distinct.

Thus each full tiling contributes $12$ distinct solutions to (a). Since there are exactly $2$ full tilings and every solution of (a) arises by deleting exactly one pentomino from a full tiling, the total number of solutions is $2\cdot 12=24$.

Therefore,

$$ \boxed{24}. $$

(b)

In any solution of (a), the set of five uncovered cells is exactly the cell set of a single pentomino from a complete tiling of the $3\times 20$ board. Every pentomino is connected by edge adjacency, hence its cell set contains pairs of cells at king distance $1$.

Kingwise nonadjacency requires that no two of the five uncovered cells are at Chebyshev distance $1$. This condition is violated by every connected 5-cell polyomino shape, since any connected pentomino contains at least one pair of edge-adjacent cells, hence also king-adjacent.

Therefore no solution of (a) satisfies the condition, and the number is

$$ \boxed{0}. $$

(c)

A solution for a $3\times 19$ board with eleven pentominoes covers $55$ cells of a $57$-cell region, leaving exactly two uncovered cells.

Extend the board to $3\times 20$ by adjoining one column. Any placement of eleven pentominoes in $3\times 19$ extends to a partial covering of the $3\times 20$ board with eleven pentominoes and two additional empty cells in the added column. Conversely, restricting any configuration on $3\times 20$ to the first $19$ columns yields a configuration on $3\times 19$ if and only if no pentomino crosses the removed boundary column.

In both full tilings of the $3\times 20$ board, inspection of the structure of (36) shows that each pentomino placement intersects every vertical cut in a way that couples the full width cyclically, so that removing a single column necessarily cuts at least one pentomino into a disconnected fragment, which is impossible in a valid pentomino placement. Hence no restriction of either full tiling yields a valid 11-pentomino covering of $3\times 19$.

Since every candidate configuration for $3\times 19$ would extend to such a restriction, no solutions exist.

Therefore,

$$ \boxed{0}. $$

This completes the solution. ∎