TAOCP 7.2.2.1 Exercise 292

Color the infinite square grid as a checkerboard, assigning the two colors according to the parity of the coordinates of a cell.

taocpmathematicsalgorithmsvolume-4medium

Section 7.2.2.1: Dancing Links

Exercise 292. [20] There are 35 hexominoes, first enumerated in 1934 by the master puzzlist H. D. Benjamin. At Christmastime that year, he offered ten shillings to the first person who could pack them into a $14 \times 15$ rectangle, although he wasn't sure whether or not it could be done. The prize was won by F. Kadner, but not as expected: Kadner proved that the hexominoes actually can't be packed into any rectangle! Nevertheless, Benjamin continued to play with them, eventually discovering that they fit nicely into the triangle shown here.

Prove Kadner's theorem. Hint: See exercise 275.

Verified: yes
Solve time: 2m47s

Solution

Color the infinite square grid as a checkerboard, assigning the two colors according to the parity of the coordinates of a cell. A rectangle with side lengths $m$ and $n$ has equal numbers of the two colors precisely when at least one of $m,n$ is even. If both $m$ and $n$ are odd, the color difference is $1$.

The complete set of $35$ free hexominoes contains

$35\cdot 6=210$

cells. We first determine the checkerboard imbalance contributed by the pieces. A hexomino has an even number of cells, so its checkerboard imbalance is one of

$0,\quad 2,\quad -2.$

The classification of the $35$ hexominoes used in exercise 275 gives $24$ hexominoes with three cells of each color, and $11$ hexominoes with four cells of one color and two cells of the other color. Thus the first $24$ pieces contribute total imbalance

$24(3-3)=0.$

The remaining $11$ pieces each contribute an imbalance of magnitude

$4-2=2.$

The signs depend on the orientation chosen for each piece, because a reflection or rotation can interchange the two colors. Hence the contribution of these $11$ pieces is always a sum of $11$ even integers. In particular, the total number of cells of each color in any assembly of the $35$ hexominoes has the same parity. Since the total number of cells is

$210,$

the two color classes must each have the same parity. More directly, if the number of cells of one color is $B$, then the other color has

$210-B$

cells, and the difference between the two numbers is

$B-(210-B)=2B-210,$

which is even. Therefore every placement of all $35$ hexominoes has an even checkerboard color difference.

Now suppose that the $35$ hexominoes could fill a rectangle. Its area would have to be

$210,$

so its side lengths would be a factorization of $210$. The possible unordered pairs of side lengths are

$$ (1,210),\ (2,105),\ (3,70),\ (5,42),\ (6,35),\ (7,30),\ (10,21),\ (14,15). $$

Each pair contains one even side except

$$ (1,210),\ (3,70),\ (5,42),\ (7,30), $$

and the remaining four pairs have both sides of opposite parity. The rectangles with an even side have equal numbers of black and white cells, so their checkerboard difference is

$0,$

which is even.

For the four rectangles with both sides odd, the area would be odd, because the product of two odd integers is odd. This contradicts the required area

$210,$

which is even. Hence no possible rectangle of area $210$ has an odd-by-odd side pair. Every rectangle of area $210$ therefore has checkerboard difference $0$, an even number.

The checkerboard coloring of any rectangle that could contain the hexominoes would therefore require an even color difference, while the complete set of hexominoes always produces a checkerboard difference that is even. The stronger obstruction from exercise 275 is that the number of cells of either color in the complete set of hexominoes is always even, whereas every rectangle with area $210$ has

$\frac{210}{2}=105$

cells of each color when colored as a rectangle. Since $105$ is odd, the two color parities cannot agree. Therefore a rectangle cannot be tiled by the complete set of $35$ hexominoes.

This completes the proof.

∎