Figures of Constant Width on a Chessboard

NEW

Problem: Let $B_n=\{0,\dots,n-1\}^2$. A figure $F\subseteq B_n$ has constant width $w$ if every row, column, and ordinary diagonal $i-j=d$ or $i+j=s$ meets $F$ in either $0$ or $w$ squares. Let $W(n,k,w)$ count constant-width figures with $|F|=kw$. The conjecture says:

Result: The conjecture is false. There is a figure of type $(4,4,2)$, but none of type $(5,5,2)$.

A $(4,4,2)$ example is

Each row and column has two points. The occupied $i-j$ diagonals are $-2,-1,1,2$, each with two points, and the occupied $i+j$ diagonals are $1,2,4,5$, each with two points. Hence $W(4,4,2)>0$.

Now suppose, for contradiction, that $F\subseteq B_5$ has type $(5,5,2)$. Then every row and column contains exactly two points. Let

Since every nonempty diagonal contains exactly two points, $|S|=|D|=5$. Also length-one diagonals cannot be occupied, so

Row and column sums give

Thus

Put $T=\{s-4:s\in S\}$. Then $T,D$ are five-element subsets of

with sum $0$.

Using second moments,

Since $(i+j)^2+(i-j)^2=2(i^2+j^2)$,

But $s=t+4$, $\sum_{t\in T}t=0$, so

A five-element zero-sum subset of $E$ is obtained by deleting one of the pairs $\{\pm1\},\{\pm2\},\{\pm3\}$. Its square-sum is respectively $26,20,10$. Therefore both $T$ and $D$ must have square-sum $20$, so

Hence

The diagonal $i+j=4$ is therefore occupied and must contain two points. But for any point on it, $i-j\equiv i+j\equiv0\pmod2$. The only even element of $D$ is $0$, so the only possible occupied point on $i+j=4$ is $(2,2)$. Contradiction.

Thus $W(5,5,2)=0$, while $W(4,4,2)>0$. Since $5\ge4$, the conjecture fails.

Citation: Definitions and conjecture: Janko Hernández and Leonel Robert, “Figures of Constant Width on a Chessboard,” American Mathematical Monthly 112 (2005), 42–50. The counterexample proof above is self-contained.