Chess board problem

combinatorics

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

We will prove the general case: In a $ n \times n$ board filled with integers $1$ to $n^2$, then there exist 2 neighboring squares whose difference is at least $n$.

Explanation of main idea: Find $n$ distinct pairs of neighbors where one term is $\leq K$ and the other neighboring term is $\geq K+1$. Then, the smallest of this terms is at most $K-n+1$, and it's neighbour is at least $K+1$, so their difference is at least $n$.

For each row, let $r_i$ be the largest number in that row.
For each column, let $c_i$ be the largest number in that column.
Let $N$ be the smallest of these $2n$ values. WLOG $N=r_I$, and cell $(I,J)$ is equal to $N$. Then, every other integer in this row is $\leq N-1$.
For every column not equal to $J$, we can find adjacent cells where one is $\leq N-1$ (starting with row $I$) and one is $\geq N+1$ (otherwise, this contradicts the minimality of $N$).

In column $J$, either $N$ is adjacent to a number $<N$, or to a number $>N$.

Case 1:$N$ is adjacent to a number $< N$
We now have $n$ distinct pairs of neighbors (since they are in different columns) where one term is $\leq N-1$ and the other is $\geq N$. Let the smallest of the terms be $S$, then $S \leq N-n$. Hence, the difference between $S$ and its neighbor is at least $n$.

Case 2:$N$ is adjacent to a number $> N$.
We now have $n$ distinct pairs of neighbors (since they are in different columns) where one term is $\leq N$ and the other is $\geq N+1$. Let the smallest of the terms be $S$, then $S \leq N-n+1$. Hence, the difference between $S$ and its neighbor is at least $n$.

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

Prove that all prime divisors of $7a^2(a+1)-1$ are of the form $7k\pm1$

Proving that $\omega(N)\neq4$ for an odd perfect number $N$ by hand

Prove this inequality $a^{\frac{a}{b}}b^{\frac{b}{c}}c\geq1$

The definition of NMSE (normalized mean square error)

Proving equivalence of a tree-based version of Countable Choice for families of finite sets.

Star of David Math Puzzle

Showing continuity of partially defined map

Does this sequence always give a square number?

Prove that $\sum_{q=0}^{d-r}\sum_{s=r+q}^{d}{{\binom {r-1+q}{r-1}}(r-1)!s}=\sum_{s=r}^{d}{\binom{s}{r}(r-1)!s}$ by sum manipulation [closed]

Which conditions must fulfill $f(t)$ to have an absolute-integrable Fourier Transform $F(w)$: $\int\limits_{-\infty}^\infty |F(w)| dw < \infty$?