Chess board problem

Is it possible to write the numbers 1, 2, ..., 25 on the square of a 5 by 5 chess board (one number per square) such that any two neighbouring numbers differ by at most 4?

(Two numbers are neighbours if they are written on squares that share a side.)

Thanks, the problem was from a maths olympiad so it might prove to be quite a tricky one :/

Any help is appreciated! Thanks! :)

• Exhaustive search on a computer showed that the answer is no, it is not possible. I do not know how to prove this, but hopefully sharing this result will prevent others from wasting time trying to prove the opposite. – Joe K Mar 21 '13 at 20:52
• Generalizaing Joe's computation, I believe for an $n\times n$ chessboard we can achieve an arrangement of the numbers $1,\ldots,n^2$ such that the difference between any neighbors is at most $n$, but no such arrangement exists for $n-1$. Although I too am unsure how to prove it. – Jared Mar 21 '13 at 20:54
• Hahaha exhaustive search XD Thanks Joe K – BittersweetNostalgia Mar 21 '13 at 20:59

Okay, let me give this a bash.

With the view to obtain a contradiction, assume that there is a way of writing the numbers $1, 2, ..., 25$ on the squares of the board in such a way that all neighbours differ by at most 4.

Let us name the rows on the board $1, 2, 3, 4, 5$ across and similarly for the columns $1, 2, 3, 4, 5$ down, for convenience. So square $(1;1)$ is the top left corner and $(5;5)$ is the bottom right corner.

Note that if $x$ is written on square $(i;j)$, then square $(i+1;j+1)$ (or any square that is diagonally neighbours from $(i;j)$ is at most $x+7$, because squares $(i;j+1)$ and $(i+1;j)$ contain maximal numbers $x+3$ and $x+4$ in some order.

Firstly, the number $1$ must be written in some edge square because if it's not, then it will need to have neighbours $2, 3, 4$ and $5$, but then $2$ would need to have two neighbours that are not in the above list which makes the difference bigger than $4$. So $1$ must be written on some edge of the board.

If it is written on, say, $(2;1)$, then squares $(3;2), (4;3), (5;4)$ contain maximal numbers $8, 15$ and $22$ respectively. But this leaves only the square $(5;5)$ for both $24$ and $25$, which is an impossibility.

If $1$ is written on square $(3;1)$, then square $(5;5)$ contains a number not more than $1+2$ x $7+2$ x $4$ = $23$, leaving no square for $25$. By a dual argument (using $25$ instead of $1$) it follows that $25$ should be written on a corner square as well.

Let us assume that $1$ is written on square $(1;1)$ and $25$ on square $(5;5)$. Then the numbers $2, 3, 4$ must be written on squares from the set ${(2;1),(1;2),(3;1),(2;2),(1;3)}$.

In particular, the number $3$ must be written on either $(1;2)$ or $(2;1)$: Assume that $3$ is written on square $(3;1)$. Then squares $(4;2)$ and $(5;3)$ contain maximal values of $10$ and $17$ respectively, implying that squares $(4;5)$ and $(5;4)$ contain maximal numbers $22$ and $21$ respectively. As before, this leaves only square $(5;5)$ open for $23, 24$ and $25$ which is impossible. A similar argument applies for when $3$ is written on $(1;3)$.

If $3$ is written on square $(2;2)$, then squares $(3,3),(4;4),(5;5)$ contain maximal numbres $10, 17$ and $24$ respectively, leaving no square for $25$ to be written on. As $2 < 3$, it cannot be writen (for the same reason) on any of $(1;3),(2;2),(3;1)$, so $2$ and $3$ must occupy squares $(1;2)$ and $(2;1)$, in some order.

We now find that there is no room for 4 on the board. If it goes onto square $(3;1)$ or $(1;3)$, we have maximal numbers $23$ and $22$ on squares $(4;5)$ and $(5;4)$ (in some order), leaving once again only one square for both $24$ and $25$.

This gives us the required contradiction, so I believe the problem is solved: No, it is not possible to write the numbers on a chessboard as such.

I hope this makes some sense, and I'm open for any fixes or suggestions. Cheers

• I believe this is a legitimate and... Correct answer. Thanks! :) – BittersweetNostalgia Mar 21 '13 at 21:12
• "Firstly, the number 1 must be written in some corner square": I think you mean edge square. "...because if it's not, then it will need to have neighbours 2,3,4 and 5, but then 2 would need to have a neighbour that is not in the above list which makes the difference bigger than 4." I think you mean: 2 would need to have two neighbours... This is your first substantial sentence, and it already has two errors. So I stopped there. – TonyK Mar 21 '13 at 21:38
• Oh right, thanks for the corrections TonyK! – mathsnoob Mar 22 '13 at 5:15
• How do you justify your eighth paragraph ("Let us assume...")? – TonyK Mar 22 '13 at 7:33
• @TonyK The preceding three paragraphs rule out all other options [except rotations and reflections], although some steps are skipped (it could be more explicit that the reasoning for (2; 1) and (3; 1) applies to all other edge squares, and 1 and 25 can't be on the same edge). – Brilliand Dec 29 '17 at 22:20