66th Belarusian Mathematical Olympiad

Answer: $n\equiv 1(\mathrm{mod}3)$.

We say that a cell is black if this cell becomes black in the final coloring, and white if this cell becomes white in the final coloring. It is easy to see that we have $2n^2+2n+1$ black and $2n^2+2n$ white cells in the chess coloring of the given table with black corner cells. In particular, we have even number of white cells and odd number of black cells.

Since each of $2n^2+2n+1$ black cells must be recolored odd number of times and each of $2n^2+2n$ white cells must be recolored even number of times (may be, zero), the total number of the recolorings is odd. Per move odd number (namely, three) cells are recolored, so the number of moves is odd.

Now we show that if $n\not\equiv 1(\mathrm{mod}3)$, then the number of moves to obtain the final coloring must be even, so one cannot obtain the final coloring for such $n$.

Fig. 1 Fig. 2

Let $A$, $B$, $C$, $D$ denote the vertices of the $(2n+1)\times (2n+1)$ square (see Fig. 1). Consider any line parallel to the line $BD$ (see Fig. 1) and passing through the centers of some cells. We call the set of all cells with the centers on such line a diagonal (see Fig. 1, where 4 from 13 possible diagonals of the $7\times 7$ square are indicated). It is evident that there are $4n+1$ distinct diagonals starting from the cells of the half-perimeter $ABC$, and each diagonal consists of either black cells (we call such diagonal black) or white cells (we call such diagonal white).

We number the cells of the half-perimeter $ABC$ as shown in Fig. 2. Consider the diagonals starting from the cells with the numbers which are divisible by 3 (let $D_3$ be the set of these diagonals), and write the symbol "" in the cells of these diagonals (see Fig. 3 and Fig. 4 for $n=2$ and $n=3$, respectively). Find the parity of the number of the black cells with "". It is evident that the diagonal from $D_3$ starting from the cell with even (odd) number is white (black). It is also evident that the diagonal starting from the cell with odd number consists of odd number of the cells. Hence, the parity of the number of the black cells with "" is equal to the parity of the number of all odd numbers (divisible by 3) between 1 and $4n+1$.

Fig. 3 Fig. 4

If $n\equiv 0(\mathrm{mod}3)$, i.e., $n=3k$, $k\in \mathbb{N}$, then $4n+1=12k+1$ and between 1 and $4n+1$ odd numbers which are divisible by 3 have the forms $3\cdot 1,3\cdot 3,\dots ,3\cdot (4k-3),3\cdot (4k-1)$. There are $2k$ such numbers.

If $n\equiv 1(\mathrm{mod}3)$, i.e., $n=3k+1$, $k\in \mathbb{N}\cup \{0\}$, then $4n+1=12k+5$ and between 1 and $4n+1$ odd numbers which are divisible by 3 have the forms $3\cdot 1,3\cdot 3,\dots ,3\cdot (4k-1),3\cdot (4k+1)$. There are $2k+1$ such numbers.

If $n\equiv 2(\mathrm{mod}3)$, i.e., $n=3k+2$, $k\in \mathbb{N}\cup \{0\}$, then $4n+1=12k+9$ and between 1 and $4n+1$ odd numbers which are divisible by 3 have the forms $3\cdot 1,3\cdot 3,\dots ,3\cdot (4k+1),3\cdot (4k+3)$. There are $2k+2$ such numbers.

Therefore, the symbol "" is written in the even number of black cells if $n\not\equiv 1(\mathrm{mod}3)$, and the symbol "" is written in the odd number of black cells if $n\equiv 1(\mathrm{mod}3)$. Suppose one can obtain the final coloring after some moves. It is easy to see that per move exactly one cell with "" is recolored. Hence we can divide all moves into two sets: the set $W$ consists of the moves when some white cell (with "") is recolored and the set $B$ consists of the moves when some black cell (with "") is recolored. There are even number of the moves from $W$ because any recolored white cell is recolored even number of times; there are also even number of moves from $B$ if $n\ne 1(\mathrm{mod}3)$, since in this case we have even number of black cells with "*" and each of them must be recolored odd number of times. Therefore, one must make even number of moves, contrary to our previous statement about the parity of the moves for $n\ne 1(\mathrm{mod}3)$. Thus, for $n\ne 1(\mathrm{mod}3)$ one cannot obtain the required chess coloring of the table.

If $n\equiv 1(\mathrm{mod}3)$, i.e., $2n+1$ is divisible by 3, one can obtain the required coloring. It suffices to divide the $(2n+1)\times (2n+1)$ table into the $3\times 3$ squares and in each such square make the moves depending on the arrangement of the black cells in this square as it is shown in Fig. 5 or Fig. 6, where the moves are shown as the segments connecting the centers of the recolored cells.

Fig. 5 Fig. 6