Putnam 2019, Problem B-6

Let \(\mathbb{Z}^n\) be the integer lattice in \(\mathbb{R}^n\). Two points in \(\mathbb{Z}^n\) are called neighbors if they differ by exactly \(1\) in one coordinate and are equal in all other coordinates. For which integers \(n \geq 1\) does there exist a set of points \(S \subset \mathbb{Z}^n\) satisfying the following two conditions?
1. If \(p\) is in \(S\), then none of the neighbors of \(p\) is in \(S\).
2. If \(p \in \mathbb{Z}^n\) is not in \(S\), then exactly one of the neighbors of \(p\) is in \(S\).


Solution:
Such a set exists for every $n$. To construct an example, define the function $f: \mathbb{Z}^n \to \mathbb{Z}/(2n+1)\mathbb{Z}$ by
$$f(x_1, \ldots, x_n) = x_1 + 2x_2 + \cdots + nx_n \pmod{2n+1},$$
then let $S$ be the preimage of 0.

To check condition (1), note that if $p \in S$ and $q$ is a neighbor of $p$ differing only in coordinate $i$, then
$$f(q) = f(p) \pm i \equiv \pm i \pmod{2n+1}$$
and so $q \notin S$.

To check condition (2), note that if $p \in \mathbb{Z}^n$ is not in $S$, then there exists a unique choice of $i \in \{1, \ldots, n\}$ such that $f(p)$ is congruent to one of $+i$ or $-i$ modulo $2n+1$. The unique neighbor $q$ of $p$ in $S$ is then obtained by either subtracting 1 from, or adding 1 to, the $i$-th coordinate of $p$.

**Remark.** According to Art of Problem Solving (thread c6h366290), this problem was a 1985 IMO submission from Czechoslovakia. For an application to steganography, see: J. Fridrich and P. Lisoněk, Grid colorings in steganography, IEEE Transactions on Information Theory 53 (2007), 1547-1549.