8.4. What is the maximum number of cells in an $n \times n$ square, drawn on graph paper, that can be colored so that no $2 \times 2$ square contains three colored cells?

## rectangular city
8.4. Answer. $n^{2} / 2$, if $n$ is even, and $\left(n^{2}+n\right) / 2$, if $n$ is odd.

Examples where exactly this number of cells are shaded are easy to construct; you need to shade all rows with odd numbers: 1st, 3rd, etc. (check this).

We also need to prove that it is impossible to shade more cells. For even $n=2 k$, this is clear, the square $2 k \times 2 k$

![](https://cdn.mathpix.com/cropped/2024_05_21_20eb9f6ef2c568605a63g-61.jpg?height=432&width=447&top_left_y=624&top_left_x=147)

Fig. 8.4. can be divided into $k^{2}$ squares $2 \times 2$, and in each of them, there should be no more than two shaded cells. For odd $n=2 k+1$, we can consider $k^{2}+k$ squares $2 \times 2$, shaded on the diagram (where $k=7$). In each of them, no more than 2 cells are shaded. Even if all $k$ cells lying on the diagonal and not covered by the shaded squares $2 \times 2$ are shaded, there will still be no more than $2\left(k^{2}+k\right)+k=\left(n^{2}+n\right) / 2$ shaded cells.