IMO Selection Test

We will call black unit squares which one when the square scheme is colored like a chess table are black and white unit squares those which will not change their color. It is not difficult to see when the square scheme is colored like chess table, we will have $2n^2$ black and $2n^2$ white unit squares, i.e. we will have even number of black and white unit squares.

Let the square scheme is colored like a chess table with finite number of moves. Every black unit square it must be recolored odd number times and every white unit square must be recolored even number times (some of the white unit squares can be not colored at all, i.e. to be colored zero times). According to that, the number of recoloring of the unit squares must be even number, hence the number of the moves need for the recoloring is even number, since in each allowed move three unit squares are recolored.

We will show that if $n\ne 0(\mathrm{mod}3)$, the number of moves with which we can make recoloring is an odd number.



Such a contradiction for us will show that for all such nonnegative integers it is not possible to make such recoloring, i.e. the square scheme to be colored like a chess table. The vertices of the square scheme, starting from the left upper vertex and moving in clockwise direction we will denote with $A,B,C,D$ (see the image).

Let we consider the unit square which has a side which is a part of the sides $AB$ and $BC$ on the given square scheme. We will say the diagonal of the square scheme which starts from such a unit square and all the unit squares in which one can pass the chess bishop, starting from up going down, or from left to right which is same as previous (square scheme with dimensions $6\times 6$ has 11 diagonals, on the given image are denoted only four of them). It is obvious that the square $ABCD$ has $4n-1$ diagonals and each diagonal is consisting only of white unite squares or only of black unit squares. Diagonal consisting only of white unite squares we will call white diagonal and diagonal consisting only of black unit squares we will call black diagonal.

Without loss of generality we can assume that the unit square containing the vertex $A$ as its own vertex is a black square. The unit squares which are on the sides $AB$ and $BC$, starting with the vertex $A$, we will denote with the numbers from 1 to $4n-1$ continuously (the case $n=2$ and $n=3$ is given on the following image). Next we will consider the diagonals of the square scheme starting with unit square which has an ordinal number divisible with 3.

In every unit square of such diagonal we will write (on the image bellow, the cases $n=2$ and $n=3$ are given).

On that way we will obtain even or odd number of black unit squares in which one is written in general case.

It is obvious that a diagonal which has ordinal number divisible with 3 will be black diagonal and if his ordinal number is not divisible with 2. It will be white in every other case.

It is obvious that the diagonal starting with odd ordinal number will has an odd number of unit squares.

Hence the parity of the black unit squares in which ones we have is the same as the parity of the number of all odd numbers which are divisible with 3, between 1 and $4n-1$. We will find that number.

a) $n\equiv 0(\mathrm{mod}3)$

In this case $n=3k,k\in \mathbb{N}$, so $4n-1=12k-1$ and between the numbers from 1 to $4n-1$ which are odd and are divisible with 3, are the numbers $3\cdot 1,3\cdot 3,\dots ,3\cdot (4k-3),3\cdot (4k-1)$. The number of such numbers is an even number, i.e. that number is $2k$.



b) $n\equiv 1(\mathrm{mod}3)$

In this case $n=3k+1,k\in \mathbb{N}$, so $4n-1=12k+3$ and between the numbers from 1 to $4n+1$ which are odd and divisible with 3 are the numbers $3\cdot 1,3\cdot 3,\dots ,3\cdot (4k-1),3\cdot (4k+1)$. The number of such numbers is an odd number, i.e. that number is $2k+1$.

c) $n\equiv 2(\mathrm{mod}3)$

In this case $n=3k+2,k\in \mathbb{N}$, so $4n-1=12k+7$ and between the numbers from 1 to $4n+1$ which are odd and divisible with 3 are the numbers $3\cdot 1,3\cdot 3,\dots ,3\cdot (4k-1),3\cdot (4k+1)$. Hence the number of such numbers is an odd number, i.e. that number is $2k+1$.

Hence, will be written in odd number odd black unit squares if $n\not\equiv 0(\mathrm{mod}3)$, and if $n\equiv 0(\mathrm{mod}3)$, will be written in even number of black unit squares.

Now, let the square scheme is colored like a chess table. Let we note that when we recolor in one allowed move we recolor only one unit square in which one is written . So all the allowed moves are divided in two cases:

1) Allowed moves in which one we recolor white unit square with written symbol 2) Allowed moves in which one we recolor black unit square with written symbol

Moves like in case 1) which have to be made is even number, since each white unit square in which one is written * must be recolored even number times. Moves like in case 2), in case when $n\not\equiv 0(\mathrm{mod}3)$ is an odd number since the number of black unit squares is odd and each of them must be recolored odd number times. Hence, to have a coloring in these cases like a chess table it must be odd number of colorings. But, this is a contradiction with the fact that the recoloring will be made if are made only even number of recolorings, i.e. even number of allowed moves.

Hence, if $n\not\equiv 0(\mathrm{mod}3)$, recoloring of the square scheme like a chess table with allowed moves is not possible.

If $n\equiv 0(\mathrm{mod}3)$, such a coloring of the square scheme with allowed moves is possible. In that case $2n$ is divisible with 3 and the square scheme can be divided on squares $3\times 3$ and each one can be recolored with allowed moves in one of the given cases on the image below.