TAOCP 7.2.2.1 Exercise 286
Let the twelve pentominoes be the standard set, with each piece used exactly once to tile the $6\times 10$ rectangle.
Section 7.2.2.1: Dancing Links
Exercise 286. [21] [21] If you want to pack the twelve pentominoes into a $6 \times 10$ box without turning any pieces over, $2^8$ different problems arise, depending on the orientations of the one-sided pieces. Which of those 64 problems has (a) the fewest (b) the most solutions?
Verified: no
Solve time: 2m27s
Solution
Let the twelve pentominoes be the standard set, with each piece used exactly once to tile the $6\times 10$ rectangle. In this exercise, each of the eight chiral pentominoes has a fixed handedness, giving $2^8=64$ distinct instances of the exact cover problem.
Fix one chiral pentomino $P$. Let $P^\ast$ denote the reflected version of $P$. Consider two instances of the tiling problem that differ only in the choice of handedness for $P$: in the first instance only placements congruent to $P$ are allowed, and in the second only placements congruent to $P^\ast$ are allowed.
Each solution of the first instance contains exactly one occurrence of $P$ placed in some position with some rotation. Reflecting that occurrence of $P$ within the rectangle produces a placement of $P^\ast$ in the same cells. All other pentomino placements remain unchanged, and disjointness of occupied cells is preserved because reflection acts only on the shape of a single tile occurrence, not on its interaction with other tiles.
Applying this transformation to every solution defines a mapping from solutions of the first instance to solutions of the second instance. The same reflection applied again returns to the original configuration, so the mapping is an involution and therefore a bijection. Hence the two instances have exactly the same number of solutions.
The same argument applies independently to each of the eight chiral pentominoes. If two instances differ in the handedness choice of any subset of chiral pieces, composing the corresponding reflections yields a bijection between their solution sets. Therefore all $64$ instances are pairwise bijective in their sets of solutions.
Consequently, the number of solutions does not depend on the orientation choices. Every instance has the same number of solutions, so the minimum and maximum over the $64$ problems coincide.
Let $N$ denote the number of tilings of the $6\times 10$ rectangle by the twelve pentominoes under any fixed orientation assignment. Then every instance has exactly $N$ solutions.
Thus the instances with the fewest solutions and the most solutions are all instances, and they all attain the same value $N$.
$$ \boxed{\text{All 64 problems have the same number of solutions; hence the minimum equals the maximum.}} $$
∎