Question

The positive integers from 1 to $n^2(n\ge 2)$ are placed arbitrarily on squares of an $n\times n$ chessboard. Prove that there exist two adjacent squares (having a common vertex or a common side) such that the difference of the number placed on them is not less than n+1.

• A. $n^2$ and 1 is less than $(n+1)(n-1)=n^2-1,$ a contradiction.
• B. $n^2$ and 1 is less than $(n-1)=n^2-1,$ a contradiction.
• C. $n^2$ and 1 is less than $(n+1)(n+1)=n^2-1,$ a contradiction.
• D. $n^2$ and 1 is less than $(n-1)(n-1)=n^2-1,$ a contradiction.

Answer 1

The correct option is A $n^2$ and 1 is less than $(n+1)(n-1)=n^2-1,$ a contradiction.

Suppose the contrary: the difference of the numbers placed in any adjacent squares is less than $n+1$. If we place a king on a square of the chessboard, it can reach any other square with number $1$ and move it to the square with number $n^2$ in at most $n-1$ moves. At each move, the difference between the numbers in the adjacent squares is less than $n+1$, hence the difference between $n^2$ and $1$ is less than $(n+1)(n-1)=n^2-1$, a contradiction