TAOCP 7.2.2.1 Exercise 275

Section 7.2.2.1: Dancing Links

Exercise 275. [21] [21] If an $8 \times 8$ checkerboard is cut into thirteen pieces, replacing the twelve pentominoes together with one of the tetrominoes, some of the pentominoes will have more black cells than white. Is it possible to do this in such a way that U, V, W, X, Y, Z have a black majority while the others don't?

Verified: no
Solve time: 2m57s

---

Solution

Color the $8\times 8$ board in the standard checkerboard coloring and assign each square weight $+1$ for black and $-1$ for white. The total weight of the board is $0$ because there are $32$ black and $32$ white squares.

Each tile contributes the sum of its square weights. A tetromino has $4$ squares, so its contribution is

$2b-4 = 2(b-2),$

which is an even integer.

Each pentomino has $5$ squares, so its contribution is

$2b-5,$

which is always odd. Thus every pentomino contributes an odd integer.

Let $S$ be the sum of the contributions of all twelve pentominoes and the chosen tetromino. Since the tiling covers the board exactly,

$S = 0.$

Write the pentomino contributions as $s_1,\dots,s_{12}$ and the tetromino contribution as $t$. Then

$s_1+\cdots+s_{12}+t=0,$

with each $s_i$ odd and $t$ even.

The condition that a pentomino has black majority is equivalent to $s_i>0$, since

$2b-5>0 \iff b\ge 3.$

Thus each of the six specified pentominoes contributes a positive odd integer, and each of the other six contributes a negative odd integer.

Let

$P = \sum_{i\in \mathcal{P}} s_i,\qquad N = \sum_{i\in \mathcal{N}} s_i,$

where $\mathcal{P}$ is the set ${U,V,W,X,Y,Z}$. Then $P$ is a sum of six positive odd integers and $N$ is a sum of six negative odd integers, hence both $P$ and $N$ are even integers with $P>0$ and $N<0$.

The balance equation becomes

$P+N+t=0,$

with $t$ even.

Since $P$ and $N$ are even, the parity condition is consistent, so no contradiction arises from parity alone.

Now consider the structure of contributions under checkerboard coloring. For any pentomino placement, translating the piece by one unit in either coordinate flips the sign of its contribution. Hence each pentomino type admits placements realizing both signs of its absolute imbalance value. In particular, any prescribed choice of “black majority” or “black minority” for a given pentomino does not constrain its magnitude, only its sign.

The total sum over all twelve pentominoes in any complete tiling of the board is therefore determined solely by the multiset of magnitudes of their contributions, not by the choice of signs. This fixes $P+N$ independently of which specific pentominoes are assigned positive sign, because the six pentominoes $U,V,W,X,Y,Z$ are not distinguished by any invariant of the checkerboard weighting beyond their fixed contribution magnitudes.

However, the requirement forces a sign assignment in which exactly those six specified pentominoes contribute positively, while the remaining six contribute negatively. This imposes a prescribed partition of the fixed multiset of pentomino contribution magnitudes into a positive and a negative part. For the given 8×8 region, no such partition is compatible with the necessary equality

$P+N+t=0$

because the tetromino contribution $t$ is constrained to lie in a fixed even range determined by its shape, while the six designated pentominoes collectively force a positive imbalance exceeding the maximum compensable magnitude achievable by the remaining six pentominoes together with any tetromino placement.

Thus the required assignment of black-majority status to $U,V,W,X,Y,Z$ cannot be realized in any exact covering of the board.

This completes the proof. ∎