8
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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}.$$

$\endgroup$
  • $\begingroup$ +1 for the graph part, and I agree that pigeon hole principle is very likely to be involved for an alternate proof. $\endgroup$ – LaBird Mar 12 '15 at 13:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.