3. In a square grid of cells, some cells are painted black. It turned out that no black cell shares a side with more than one other black cell? What is the maximum number of cells that could be painted black?

In a square of cells, some cells are painted black. It turned out that no black cell shares a side with more than one other black cell? What is the maximum number of cells that could be painted black?
Solution. An example of properly coloring 8 squares is shown in Fig. 1a. Suppose more than 8 were colored, then at least one of the four $2 \times 2$ squares would have at least three cells colored (Fig. 1b). But then at least one of them would share adjacent sides with two other black cells. This contradiction completes the proof.

![](https://cdn.mathpix.com/cropped/2024_05_06_7440f25d146e96f0abdbg-1.jpg?height=405&width=417&top_left_y=2202&top_left_x=363)
a)

![](https://cdn.mathpix.com/cropped/2024_05_06_7440f25d146e96f0abdbg-1.jpg?height=214&width=211&top_left_y=2406&top_left_x=1368)

b)

Fig. 1

Answer: 8.