Question

A positive integer is written in each square of an $n^2\times n^2$ chess board. The difference between the numbers in any adjacent squares (sharing an edge) is less than or equal to n. Prove that at least $\lfloor \frac{n}{2}\rfloor +1$ squares contain the same number.

• A. $n^4>(2(n^2-1)n+1)\frac{n}{2},$ more than $\frac{n}{2},$ squares contain the same number, as needed.
• B. $n^4>(2(n^2-1)n+1)\frac{n}{2},$ less than $\frac{n}{2},$ squares contain the same number, as needed.
• C. $n^4>(4(n^2-1)n+1)\frac{n}{2},$ more than $\frac{n}{2},$ squares contain the same number, as needed.
• D. None of the above

Answer 1

The correct option is A $n^4>(2(n^2-1)n+1)\frac{n}{2},$ more than $\frac{n}{2},$ squares contain the same number, as needed.

Consider the smallest and the largest numbers on the chess board as $a$ and $b$. They are atmost separated by $n^2-1$ squares horizontally and $n^2-1$ squares vertically. So there is a path between one to other with lenght at most $2(n^2-1)$. As any two successive differ by $n$, we have,

$b-a\le 2(n^2-1)n$

All the numbers on the board are integers lying between a and b. Therefore only $2(n^2-1)n+1$ numbers exists. Therefore, because $n^4>(2(n^2-1)n+1)\frac{n}{2},$, more than $\frac{n}{2}$ squares contain the same numbers.