67th NMO Selection Tests for JBMO

a. Let us notice that the sum of the 36 numbers written on the board is invariant modulo 3. When all the numbers on the board are equal, their sum is a multiple of 36, hence a multiple of 3. But this requires that the initial sum is also a multiple of 3. In conclusion, if the sum of the initial numbers is not a multiple of 3, there is no succession of moves that makes the numbers equal. In conclusion, 6 is not good.

b. For $n=4$, we choose an arbitrary unit square and prove that we can increase by 1 all the other 15 numbers from the board. For example, if the chosen square lies in the upper left $2\times 2$ corner, we successively increment the numbers in the squares marked with B, then those marked by C, D, and E. Finally, we increment 3 of the four numbers in the squares marked with A (with the exception of the chosen one). Thus, combining five moves, we have obtained a move that is equivalent to decreasing the chosen number by 1.



Repeating this new move and choosing each time the largest number (or one of those if there are several largest ones), we can make the numbers equal.

For $n$ a power of 2, in particular for $n=2^{10}=1024$, we prove by induction that any $2^k\times 2^k$ board ($k\ge 1$) from which an arbitrary unit square has been removed, can be tiled with non-overlapping L-shaped trominos (figures obtained by removing a unit square from a $2\times 2$ square).

The possibility of tiling such "deficient squares" with L-shaped trominos is a classical problem due to Golomb.

Assume the statement true for $n=2^{k-1}$ and let us prove it for $n=2^k$. Draw the center lines of the $2^k\times 2^k$ board. The cut-off square lies in exactly one of the four thus obtained $2^{k-1}\times 2^{k-1}$ boards. We may remove one square from each of the other three boards by placing a tromino at the center of the $2^k\times 2^k$ board. The result is a tromino and four $2^{k-1}\times 2^{k-1}$ boards, each with one square removed - just a situation to apply the inductive hypothesis.

This tiling allows us to construct a sequence of moves that increases by 1 the number in every square with the exception of one square that can be arbitrarily chosen. By repeatedly using such sequences we can make all the numbers of the board equal.