A rook has passed through an \$n\$×\$n\$ board, visiting each cell exactly once, and each of its moves was exactly one cell. The cells are numbered from 1 to \$n^2\$ in the order of the rook's passage. Let $\$ M \$$ be the maximum difference between the numbers of adjacent (by side) cells. What is the smallest possible value of $\$ \mathrm{M} \$$?
Example. We traverse the board in a "snake" pattern, starting from the bottom left corner: to the right to the end, up by 1, to the left to the end, up by 1, ...

Evaluation. Method 1. Assume the contrary: $M < 2n - 1$. Consider the numbers in the top row. Since the difference between any two adjacent numbers in this row is no more than $2n - 2$, the rook must have reached from the smaller of these numbers to the larger without entering the bottom row (to reach it, it would take at least $n - 1$ moves, and to return, it would also take at least $n - 1$ moves, plus one more move is made in the bottom row itself). Thus, the rook traversed all the numbers in the top row without entering the bottom row. Similarly, the rook traversed all the numbers in the bottom row without entering the top row. This means that all the numbers in the top row are greater (or all smaller) than the numbers in the bottom row. Similarly, all the numbers in the left column are greater (or all smaller) than the numbers in the right column. Without loss of generality, we can assume that the numbers in the left column are greater than the numbers in the right column, and the numbers in the bottom row are greater than the numbers in the top row. Consider two numbers - in the top left corner (number $A$) and in the bottom right corner ($B$). On the one hand, $A$ is the smallest of the corner numbers, and $B < D$. All cells along the side $AD$ will be divided into two non-empty sets, one with numbers less than $B$, and the other with numbers greater than $B$. There will be a pair of adjacent cells along the side from different sets, let their numbers be $X < Y$. The rook needed at least $n - 1$ moves to reach from $X$ to the side $BC$, at least one move along $BC$, and at least $n - 1$ more moves to reach $Y$. Therefore, $Y - X \ge 2n - 1$.

Method 2. We need to prove that there will be adjacent cells, the difference in their numbers being no less than $2n - 1$. Suppose the board is a square and consider that $A$ is the smallest of the corner numbers, and $B < D$. All cells along the side $AD$ will be divided into two non-empty sets, one with numbers less than $B$, and the other with numbers greater than $B$. There will be a pair of adjacent cells along the side from different sets, let their numbers be $X < Y$. The rook needed at least $n - 1$ moves to reach from $X$ to the side $BC$, at least one move along $BC$, and at least $n - 1$ more moves to reach $Y$. Therefore, $Y - X \ge 2n - 1$.

## Answer

$2n - 1$.

Submit a comment