10.5. How many cells need to be marked on an 8 by 8 grid so that each cell on the board, including the marked ones, is adjacent by side to some marked cell? Find all possible answers. Note that a cell is not considered adjacent to itself.
Answer: 20.

Solution: First, let's gather our strength and mark twenty cells on an 8 by 8 board as required by the problem. For example, as shown in the figure. In this case, the board naturally divides into 10 parts, as indicated by the bold lines in the figure. Each part consists of cells adjacent to the given pair of marked cells.

![](https://cdn.mathpix.com/cropped/2024_05_06_017fc8a7c4fc76b0b4b0g-2.jpg?height=494&width=397&top_left_y=2414&top_left_x=1503)

Now, using the constructed example, we will prove that the only answer to the problem is indeed 20 cells. Consider the division of the board into 10 parts as shown in the example. From now on, we will call these parts figures, as in the example. We will call the central cells of each figure those that are marked in the example in the figure. Recall that the chessboard has a natural coloring of cells in a checkerboard pattern, and consider the black and white parts of each figure, consisting of black and white cells of this figure, respectively. Note that the white central cell of a figure is adjacent only to black cells of this figure, and only to all of them, and the black central cell of a figure is adjacent only to white cells of this figure, and only to all of them.

Now consider any marking of cells on the board that satisfies the problem's condition, and prove that each figure contains exactly two marked cells, from which the answer to the problem will follow. Indeed, if some figure contains at least three marked cells, then it contains at least two white marked cells or at least two black marked cells, then the central cell of the opposite color of this figure will be adjacent to at least two marked cells, which contradicts the condition. And if some figure contains no more than one marked cell, then it either has no white marked cells or no black marked cells, then the central cell of the opposite color of this figure will not be adjacent to any marked cell, which also contradicts the condition. Therefore, each figure contains exactly two marked cells, so any example contains exactly 20 marked cells.

Note that the example constructed in this solution is not unique, and we did not prove that the marked cells of any example coincide with those marked by us. The board can be rotated by 90 degrees, and a new example different from the one considered will result, but still, each figure contains exactly two marked cells from the new example.

Remark. The estimate for 20 can also be done differently, by first proving that the number of extreme marked cells is at least 9, etc. This is a long and risky path with case-by-case analysis. When evaluating such claimed solutions, each step must be very carefully assessed, and if such a solution contains unconsidered cases or errors in calculations, the estimation part of the solution is not rated higher than 1 point.

Evaluation Criteria: (•) An example with 20 cells is constructed: 3 points. (•) It is proven that the number of marked cells is always 20: 4 points. (•) The idea of considering figures from the board solution for estimation (without significant progress): 1 point.