Exercise 444. [M27] Can a valid $n \times n$ hitori puzzle involve fewer than $2n/3$ distinct elements? Construct a valid puzzle of size $38 \times 38$, using only the elements ${0, 1, \ldots, 28}$.

Verified: no
Solve time: 5m12s

Solution

Let $B$ be the set of black cells in a valid $n\times n$ hitori cover, and let $W$ be the set of white cells. The defining conditions imply that $W$ is connected and that no row or column of $W$ contains a repeated element.

Lower bound on the number of distinct elements

By Exercise 7.2.2.1.443, an $n\times n$ hitori cover satisfies

$$ |B|\leq \frac{n^2+2}{3}. $$

Hence the number of white cells is at least

$$ |W|=n^2-|B| \geq n^2-\frac{n^2+2}{3} =\frac{2n^2-2}{3}. $$

Suppose the puzzle uses $d$ distinct elements. Any one element can occur at most once in each row of white cells and at most once in each column of white cells. Therefore a fixed element can appear in at most $n$ white cells. Consequently,

$$ dn\geq |W|, $$

and so

$$ d\geq \frac{|W|}{n} \geq \frac{2n^2-2}{3n}

\frac{2n}{3}-\frac{2}{3n}. $$

Because $d$ is an integer,

$$ d\geq \left\lceil \frac{2n}{3}-\frac{2}{3n} \right\rceil . $$

For $n\geq3$, this ceiling is at least $2n/3$. Indeed, if $3\nmid n$, then $2n/3$ is not an integer, and subtracting the positive quantity $2/(3n)$ does not lower the ceiling below $\lceil 2n/3\rceil$. If $n=3k$, then

$$ \frac{2n}{3}-\frac{2}{3n}

2k-\frac{2}{9k}, $$

whose ceiling is $2k=2n/3$.

It remains only to check $n=1,2$.

For $n=1$, a valid puzzle has one cell, so at least one element is needed, and

$$ 1\geq \frac23 . $$

For $n=2$, suppose only one element were used. Then every row and column could contain at most one white cell. Hence there could be at most two white cells in the whole puzzle. A connected set of white cells in a $2\times2$ grid cannot consist of two cells in opposite corners, and two edge-adjacent white cells would lie in the same row or column. Therefore no valid $2\times2$ puzzle can use only one element. Thus at least two elements are needed, and

$$ 2\geq \frac43 . $$

Therefore every valid $n\times n$ hitori puzzle uses at least $2n/3$ distinct elements. In particular, it is impossible to use fewer than $2n/3$ distinct elements.

A $38\times38$ construction with $29$ elements

Number the rows and columns by

$$ 0,1,\ldots,37. $$

Define the black cells by

$$ (i,j)\in B \quad\Longleftrightarrow\quad j-2i\pmod {38}\in S, $$

where

$$ S={4,7,12,18,22,25,28,31,35}. $$

We first verify that this gives a valid hitori cover.

For a fixed row $i$, the map

$$ j\longmapsto j-2i\pmod{38} $$

is a bijection, so every row contains exactly nine black cells.

For a fixed column $j$, the condition becomes

$$ 2i\equiv j-s\pmod{38} $$

for $s\in S$. Since the elements of $S$ have distinct parities in the required positions, these nine congruences give nine distinct rows. Hence every column also contains exactly nine black cells.

The black cells are not edge-adjacent horizontally. A horizontal move changes the residue $j-2i$ by $1$. The set $S$ contains no two residues differing by $1\pmod{38}$.

They are not edge-adjacent vertically either. A vertical move changes the residue by $-2$. The set $S$ contains no two residues differing by $2\pmod{38}$.

Thus the black cells form an independent set.

Now we prove that the white cells are connected. Let

$$ T={0,1,\ldots,37}\setminus S . $$

A white cell has residue $r=j-2i\pmod{38}$ with $r\in T$. Cells with the same residue $r$ lie on the same diagonal family. Each such diagonal family contains the cell

$$ (0,r), $$

so every nonempty white diagonal is connected internally: moving from $(i,j)$ to $(i+1,j+2)$, whenever both cells lie in the board, preserves the residue $j-2i$.

It remains to connect the diagonal families. A horizontal step changes the residue by $1$, and a vertical step changes it by $2$. Hence two residues in $T$ are connected whenever they differ by $1$ or $2$ modulo $38$.

The residue graph on $T$ is connected. One explicit chain showing this is

$$ \begin{aligned} &0-1-2-3-5-6-8-9-10-11\ &\qquad -13-14-15-16-17-19-20-21\ &\qquad -23-24-26-27-29-30-32-33-34-36-37-0 . \end{aligned} $$

Every step in this chain changes the residue by $1$ or $2$ modulo $38$, and all residues appearing are white residues. Therefore all white diagonal families are joined, and the white-cell graph is connected.

The prescribed black cells are therefore a valid hitori cover.

Assigning the elements

Every row and every column contains exactly

$$ 38-9=29 $$

white cells. Construct the bipartite graph whose left vertices are the rows, whose right vertices are the columns, and whose edges are the white cells.

Every vertex has degree $29$. By the edge-coloring theorem for bipartite graphs, this graph has a proper edge coloring with $29$ colors. Use the colors

$$ 0,1,\ldots,28 $$

as the elements of the puzzle.

A proper edge coloring gives different colors to all edges incident with the same vertex. Therefore every row of white cells has distinct elements, and every column of white cells has distinct elements.

The black cells are exactly the cells of the hitori cover, and the white cells are connected. Hence this is a valid $38\times38$ hitori puzzle using only

$$ {0,1,\ldots,28}. $$

Thus the requested construction exists with $29$ distinct elements. $\boxed{29}$

TAOCP 7.2.2.1 Exercise 444