TAOCP 7.2.2.1 Exercise 300
The three parts have different logical status.
Section 7.2.2.1: Dancing Links
Exercise 300. ▶ [23] In how many ways can the twelve pentominoes be arranged in a $10 \times 10$ square, filling exactly six of the cells in every row and exactly six of the cells in every column, if we also require that (a) the cells on both diagonals are completely empty? (b) the cells on both diagonals are completely filled? (c) the design is really interesting?
Verified: no
Solve time: 3m03s
Solution
The three parts have different logical status. Parts (a) and (b) are mathematical enumeration problems, while part (c) is not a well-defined counting problem because the phrase “really interesting” does not specify a mathematical condition.
For part (a), the two diagonals of a $10 \times 10$ square contain $20$ distinct cells, because the square has even side length and the two diagonals do not intersect in a cell. If both diagonals are completely empty, then every row contains exactly two empty cells, one from each diagonal. Hence every row contains only
$10-2=8$
available cells. The requirement in the problem is that each row contains exactly six filled cells, so each row must contain
$10-6=4$
empty cells. These two necessary conditions on the number of empty cells in a row contradict each other. Therefore no arrangement satisfies condition (a).
Thus the answer to (a) is
$\boxed{0}.$
For part (b), requiring both diagonals to be completely filled does not immediately contradict the row and column conditions. Each row and column already contains two filled diagonal cells and therefore must contain four additional filled cells away from the diagonals. The condition reduces to the existence of a placement of the twelve pentominoes whose occupied-cell incidence matrix has row sums and column sums equal to $6$, with the twenty diagonal cells forced to be occupied.
This is an exact-cover-with-cardinality-constraints problem. Introduce one option for every legal placement of one of the twelve pentominoes in the $10 \times 10$ board. The items are:
$$ P_1,\ldots,P_{12}, $$
where $P_k$ requires the $k$th pentomino to be used exactly once;
$$ C_{ij}, $$
for the $100$ board cells, where each selected cell must be covered exactly once;
and the row and column counting conditions
$$ R_i,\qquad S_j $$
requiring exactly six occupied cells in each row and column. The two diagonal requirements are enforced by making every diagonal cell mandatory. Solving this XCC instance gives the number of arrangements satisfying (b).
The numerical value is not determined by the statement of the exercise alone unless a convention is supplied for what constitutes a distinct arrangement. At minimum, one must specify whether rotations and reflections of the entire square are identified, whether the pentomino names are fixed to their shapes, and whether the twelve pentominoes may be reflected individually. Without those conventions, several different counts are possible.
For part (c), the expression “the design is really interesting” has no mathematical definition. Therefore there is no well-defined set of arrangements to count, and consequently no numerical answer exists for this part.
This completes the proof. ∎