66th Belarusian Mathematical Olympiad

a) 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.

We divide the $(2n+1)\times (2n+1)$ table into concentric zones with unit width, and the central cell (see Fig. 1). The central cell and all corner cells are white. The cells of any such zone can be recolored in chess order so that the corner cells remain white and only cells of such zone take part in the recoloring. Indeed, it is sufficient to make all possible moves (each move is made exactly one time) with the ends at the white cells (see Fig. 2 and Fig. 3, where it is shown for the zones of the length 16 and 24; each move is shown as the segment connecting the centers of the recolored white cells).

Fig. 1 Fig. 2 Fig. 3

In this case each white cell is recolored two times and remains white, and each black cell is recolored exactly one time and turns black. The central cell is not recolored and remains white. Therefore, using this type of the moves one can obtain the chess coloring of the given table with white corner cells.

b) If we use the algorithm from item a) to obtain the $7\times 7$ table with chess coloring, then we need $24$ moves. Show that it is sufficient $14$ moves to recolor the square.

It is easy to see that there are $24$ black and $25$ white cells in the $7\times 7$ table. Since each of $24$ black cells must be recolored odd number of times and each of $15$ white cells must be recolored even number of times (may be, zero), the total number of the recolorings is even. Per move odd number (namely, three) cells are recolored, so the number of moves is even.

Since each of $24$ black cells must be recolored at least one time and per move at most two black cells are recolored, the total number of moves is greater than or equal to $24:2=12$.

Show that $12$ moves are not sufficient. Suppose, contrary to our claim, that we obtain the finishing coloring using $12$ moves. It follows that exactly two black cells and exactly one white cell are recolored at the same move. But each white cell is recolored even number of times, so at most $12:2=6$ white cells can be recolored using these $12$ moves.

Now, we mark seven black cells as it is shown in Fig. 4 and consider their adjacent white cells, that is, those sharing a common side with the marked black cells.

Fig. 4 Fig. 5

We see that none of these white cells is adjacent to two of the marked black cells (in Fig. 4 for each marked black cell we number its adjacent white cells with the same number). When any of these seven black cells is recolored at least one adjacent white cell must be recolored, hence (the marked black cells have no common adjacent white cells) at least seven different white cells must be recolored, a contradiction. Thus, $12$ moves are not sufficient to obtain the required chess coloring square. But the total number of the moves is even, so we need at least $14$ moves.

The example (see Fig. 5, where each move is shown as the segment connecting the centers of the recolored cells) shows how to obtain the required coloring with $14$ moves.