In a 3x3 grid with 9 consecutive integers, prove there is at least one sum of 3 integers horizontally, vertically or diagonally that is divisible by 3

Question

When I read a question in this forum Maximize the prime sums in a table, I noticed that when $9$ consecutive integers are to be filled into a $3\times3$ grid, no matter how the integers are arranged, there must be at least one sum of $3$ numbers either horizontally, vertically or diagonally that can be divisible by $3$. I am interested to find a proof, but what I have achieved is to simplify the $9$ integers to become {$0$, $0$, $0$, $1$, $1$, $1$, $2$, $2$, $2$} (i.e., taking the $\mod 3$ results of the $9$ consecutive integers), and then trying them by brute force. Surely this method does not give a nice proof. Is there any better way to prove it?

Answer 1

Working over $\mathbb{Z}_3$ is a good idea. I suspect there is an elegant pigeon-hole principle argument lurking about, but here is another one.

Notice that the entries in any line (= row/column/diagonal) sums to zero (modulo $3$) if and only if all entries are equal or all are different. So suppose you have a matrix $M$ (over $\mathbb{Z}_3$) such that every line has exactly two entries that are equal.

Let's draw a bipartite graph $G$ with bipartition $(L,R)$ where the $8$ vertices of $L$ represent the $8$ different lines and $R=\{0,1,2\}$. Join a vertex $\ell\in L$ and an $x\in R$ if $x$ is an entry in the line $\ell$.

By our assumption on $M$, every vertex in $L$ has degree exactly $2$, and thus $G$ has exactly $16$ edges.

On the other hand, let's look at the degrees of the three vertices in $R$.

Claim: Every vertex $x\in R$ has degree at least $5$.

Proof: If $(i,j),(k,l),(m,n)$) are the coordinates of the $x$'s in $M$, then at least two of the row indices are distinct and at least two of the column indices are distinct. This gives at least $4$ lines (all being rows or columns). But if either the set of row indices, or the set of column vertices are distinct, then we have $5$ lines. On the other hand, if two of the row indices are equal and two of the column indices are equal, then there is a diagonal containing $x$, and so a $5$th line.

Since every vertex in $R$ has degree at least $5$, but there are only $16$ edges in $G$, we must have two vertices in $R$ with degree $5$, and one of degree $6$.

Let $x$ be the entry in the center of $M$. This entry is on $4$ lines, and so corresponds to $4$ edges in $G$. There are two more $x$'s in $M$.

Case 1: one of the other $x$'s is on a corner entry. then we get $2$ more edges in $G$ from these two lines (the corresponding row and column). So the degree of $x$ is at least $6$. Since the degree can't be higher than $6$, the final $x$ can then only be in one of two positions. Rotating/reflecting if necessary, this means that $M$ looks like: $$M=\begin{bmatrix} x & x & \cdot \\ \cdot & x & \cdot\\ \cdot & \cdot & \cdot\end{bmatrix}.$$ Let $y$ be the entry in coordinates $(1,3)$. This forces $M$ to look like: $$M=\begin{bmatrix} x & x & y \\ y & x & \cdot\\ y & \cdot & \cdot\end{bmatrix}.$$

But then we can fill in the third possible entry in one way, producing a line with distinct entries: $$M=\begin{bmatrix} x & x & y \\ \color{red}{y} & \color{red}{x} & \color{red}{z}\\ y & z & z\end{bmatrix}.$$

Case 2: None of the corner entries of $M$ equal $x$. Since not all three $x$'s are in the same line, this means that (rotating if necessary) $M$ looks like: $$M=\begin{bmatrix} \cdot & x & \cdot \\ x & x & \cdot\\ \cdot & \cdot & \cdot\end{bmatrix}.$$

Let $y$ be the entry in coordinate $(1,1)$. Then $M$ can only look like $$M=\begin{bmatrix} y & x & y \\ x & x & \cdot\\ y & \cdot & \cdot\end{bmatrix}.$$ But now we can fill in the $z$'s obtaining a line with distinct entries, a contradiction: $$M=\begin{bmatrix} \color{red}{y} & x & y \\ x & \color{red}{x} & z\\ y & z & \color{red}{z}\end{bmatrix}.$$