10
$\begingroup$

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! :)

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Joe K Mar 21 '13 at 20:52
  • $\begingroup$ 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. $\endgroup$ – Jared Mar 21 '13 at 20:54
  • $\begingroup$ Hahaha exhaustive search XD Thanks Joe K $\endgroup$ – BittersweetNostalgia Mar 21 '13 at 20:59
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I believe this is a legitimate and... Correct answer. Thanks! :) $\endgroup$ – BittersweetNostalgia Mar 21 '13 at 21:12
  • 1
    $\begingroup$ "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. $\endgroup$ – TonyK Mar 21 '13 at 21:38
  • $\begingroup$ Oh right, thanks for the corrections TonyK! $\endgroup$ – mathsnoob Mar 22 '13 at 5:15
  • $\begingroup$ How do you justify your eighth paragraph ("Let us assume...")? $\endgroup$ – TonyK Mar 22 '13 at 7:33
  • $\begingroup$ @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). $\endgroup$ – Brilliand Dec 29 '17 at 22:20

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.