TAOCP 7.2.2.1 Exercise 443
Let $B$ be the set of black cells and $W$ the set of white cells.
Section 7.2.2.1: Dancing Links
Exercise 443. ▶ [M30] Prove that an $m \times n$ hitori cover has at most $(mn + 2)/3$ black cells.
Verified: no
Solve time: 4m37s
Solution
Let $B$ be the set of black cells and $W$ the set of white cells. Put
$$ b=|B|,\qquad w=|W|. $$
Because every cell is either black or white,
$$ b+w=mn. $$
The desired inequality
$$ b\leq \frac{mn+2}{3} $$
is equivalent to
$$ 3b\leq b+w+2, $$
or
$$ w\geq 2b-2. $$
It therefore suffices to prove that the number of white cells is at least $2b-2$.
Consider the white cells as a connected polyomino. Let $P$ denote its perimeter, meaning the number of unit grid edges that have a white cell on one side and a nonwhite cell or the exterior of the rectangle on the other side.
Because black cells are pairwise nonadjacent, every side of every black cell borders a white cell or the exterior of the rectangle. Hence every side of every black cell contributes to the perimeter of the white region. Therefore,
$$ P\geq 4b. $$
We now obtain an upper bound for $P$ in terms of $w$. Let $e$ be the number of pairs of orthogonally adjacent white cells. Each such adjacency removes two unit edges from the sum of the individual perimeters of the cells, so
$$ P=4w-2e. $$
The graph induced by the white cells is connected, so it contains a spanning tree on its $w$ vertices. Consequently,
$$ e\geq w-1. $$
Substituting this into the perimeter formula gives
$$ P=4w-2e\leq 4w-2(w-1), $$
and hence
$$ P\leq 2w+2. $$
Combining the two bounds for $P$,
$$ 4b\leq P\leq 2w+2. $$
Therefore,
$$ 4b\leq 2w+2, $$
so
$$ 2b\leq w+1. $$
This gives
$$ w\geq 2b-1. $$
In particular,
$$ w\geq 2b-2. $$
Using $w=mn-b$, we obtain
$$ mn-b\geq 2b-2. $$
Rearranging,
$$ mn+2\geq 3b, $$
and therefore
$$ b\leq \frac{mn+2}{3}. $$
Thus every $m\times n$ hitori cover has at most
$$ \boxed{\frac{mn+2}{3}} $$
black cells. $\square$