A 9×9 square is divided into 81 unit cells. Some cells are shaded, and the distance between the centers of any two shaded cells is greater than 2.

a) Provide an example of a coloring where there are 17 shaded cells.

b) Prove that there cannot be more than 17 shaded cells.
b) Suppose it was possible to color 18 cells. Divide the $9 \times 9$ square into nine $3 \times 3$ squares. Label the cells of the square with horizontal coordinates as letters from $a$ to $i$, and vertical coordinates as numbers from 1 to 9. Denote the $3 \times 3$ squares with Greek letters from $\alpha$ to $\iota$, as shown in the figure on the right. It is easy to notice that a $3 \times 3$ square can contain no more than two colored cells, so each of the nine $3 \times 3$ squares contains exactly two colored cells. Among the two colored cells in a $3 \times 3$ square, one must be in a corner. Without loss of generality, we can assume that in the central square $\varepsilon$, the cell d4 is colored. Then, in the square $\alpha$, one of the corner cells a1, c1, or a3 must be colored. If the cell c1 is colored, it is impossible to color two cells in the square $\beta$ that satisfy the conditions of the problem. Similarly, it is impossible to color the square $\delta$ if we assume that the cell a3 is colored. Therefore, the cell a1 is colored. The second colored cell, without loss of generality, we will assume is c2. Then the colored cells in the squares $\beta$ and $\gamma$ are uniquely determined - e1, f3, and h1, i3. Similarly, in the squares $\zeta$ and $\iota$, the only cells that can be colored are g5, i6, g8, and i9. Returning to the central square $\varepsilon$, the second colored cell can only be e6. But then it is impossible to color two cells in the square $\theta$ while satisfying the condition. Contradiction.
![](https://cdn.mathpix.com/cropped/2024_05_06_75db48f86176e8f64efag-26.jpg?height=598&width=1198&top_left_y=913&top_left_x=433)

## Answer

a) See the figure on the left.