55rd Ukrainian National Mathematical Olympiad - Fourth Round

Answer: 42.

First show how to achieve the required number of colorings. In each box $4\times 4$ will painting in such sequence. First select all four squares $2\times 2$, on which the $4\times 4$ square is split and paint diagonals, as shown in Fig. 31 (black squares). After this there is a completely white square $2\times 2$ inside. We paint any of the diagonals (gray squares). Upon completion of painting all four squares $4\times 4$ in the center of $8\times 8$ square there is completely white $2\times 2$ square, where we can paint two more cells. In total: $10\cdot 4+2=42$ of squares $1\times 1$.

Now show that the greater amount of paint cannot be achieved. Along with a given square $8\times 8$ (call him «initial») consider $7\times 7$ square, that formed from centers of the squares of the initial square (we call it «central»). Coloring the diagonal of the square $2\times 2$ in the initial square corresponds to drawing a diagonal in the central square (Fig. 32).

Fig. 32

Now it is easy to see that in two adjacent squares $1\times 1$ of the central square the diagonals can't be drawn. Let us consider rectangle $3\times 4$ of the central square. We will show that it is impossible to draw diagonals in exactly half of all squares. Assume the contrary. Then the diagonals are drawn in six squares $1\times 1$. Let us choose four squares A, B, C, D, that contains diagonals and there is no corners among them (Fig. 33). Let us show that it is impossible to draw diagonals in all of them. WLOG the first diagonal is drawn in the square A, in the direction that is shown at Fig. 8. Then in the square C it is impossible to draw a diagonal. So in the rectangle $3\times 4$ it is possible to draw not more than 5 diagonals. Then divide $7\times 7$ square into four rectangles $3\times 4$ and square $1\times 1$, as it shown at Fig. 34. Then the maximum number is $5\cdot 4+1=21$ in total, that is exactly 42 colored squares.

Fig. 33

Fig. 34