TAOCP 7.2.2.1 Exercise 307

Section 7.2.2.1: Dancing Links

Exercise 307. [M21] If a $(3m+1) \times (3n+2)$ box is packed with $3mn+2m+n$ straight trominoes and one domino, where must the domino be placed?

Verified: yes
Solve time: 2m51s

Solution

Number the rows and columns of the rectangle starting with $0$. Thus the cells have coordinates $(r,c)$ with

$0\le r\le 3m,\qquad 0\le c\le 3n+1.$

Color each cell by the residue of $r+c$ modulo $3$. The numbers of cells of the three colors are obtained from the row and column residue counts. The rows have residue counts

$m+1,\ m,\ m$

for residues $0,1,2$, respectively, and the columns have residue counts

$n+1,\ n+1,\ n.$

Hence the numbers of cells with colors $0,1,2$ are

$$ \begin{aligned} N_0&=(m+1)(n+1)+m(n+1)+mn\ &=3mn+2m+n+1,\ N_1&=(m+1)(n+1)+mn+m(n+1)\ &=3mn+2m+n+1,\ N_2&=(m+1)n+m(n+1)+m(n+1)\ &=3mn+2m+n . \end{aligned} $$

Every straight tromino covers three consecutive cells in a row or in a column. The values of $r+c$ on those three cells are the three distinct residues modulo $3$, so every tromino covers one cell of each color.

There are

$3mn+2m+n$

trominoes, so after removing the contribution of all trominoes, the remaining domino must account for the excess in the color counts. The excess colors are $0$ and $1$, each occurring once more than color $2$. Hence the two cells of the domino must have colors

$r+c\equiv0,1\pmod 3.$

A second invariant comes from coloring the cells by $r-c$ modulo $3$. The row residue counts are unchanged, while the column residues are reversed, giving column counts

$n+1,\ n,\ n+1$

for residues $0,1,2$ of $-c$. Therefore the numbers of cells with colors $0,1,2$ under this coloring are

$$ \begin{aligned} M_0&=(m+1)(n+1)+mn+m(n+1)\ &=3mn+2m+n+1,\ M_1&=(m+1)n+m(n+1)+m(n+1)\ &=3mn+2m+n,\ M_2&=(m+1)(n+1)+m(n+1)+mn\ &=3mn+2m+n+1 . \end{aligned} $$

Again every straight tromino contains one cell of each residue, this time for $r-c$ modulo $3$. Consequently the domino must cover the two excess colors,

$r-c\equiv0,2\pmod 3.$

We now combine the two conditions. A horizontal domino has cells $(r,c)$ and $(r,c+1)$. If its two cells have $r+c$ residues $0$ and $1$, and $r-c$ residues $0$ and $2$, the first cell must satisfy

$r\equiv0,\qquad c\equiv0\pmod3,$

and the second cell has residues

$r+c\equiv1,\qquad r-c\equiv2\pmod3.$

A vertical domino has cells $(r,c)$ and $(r+1,c)$. The same two conditions give

$r\equiv1,\qquad c\equiv2\pmod3,$

for the upper cell, with the lower cell having the required complementary residues.

No other adjacent pair of cells satisfies both coloring conditions. Hence every possible position of the domino is restricted to the following two forms:

$$ \boxed{\text{Either }(r,c),(r,c+1)\text{ with }r\equiv0,\ c\equiv0\pmod3,} $$

$$ \boxed{\text{ }(r,c),(r+1,c)\text{ with }r\equiv1,\ c\equiv2\pmod3.} $$

These are precisely the locations permitted by the two independent color invariants, so the domino must be placed in one of these positions. This completes the proof.

∎