21. For any coloring of the cells of a grid board in black and white, the board is divided into monochromatic areas (with a checkerboard coloring, all areas are single-cell). Each move, Petya selects one area and repaints it to the opposite color. The repainted area merges with adjacent areas of the same color, and the number of areas decreases. What is the minimum number of moves Petya can make to turn a checkerboard-colored $13 \times 13$ board into a monochromatic board?
$\square$ Answer: in 12.

Example. With each move, we repaint the area containing the central cell.

Estimate. We glue together cells of the same color into one area not only if they touch by sides, but also if they touch by the bottom right and top left corners. Then initially we have only 17 diagonal areas, their adjacency graph forms a chain of 25 edges. With each repainting, no more than two edges are destroyed, so at least 12 repaintings are needed.

(A. Shapovalov)

## Fourth Round