11.3. Let's call the distance between two cells on a checkerboard the minimum number of moves a chess king can make to get from one to the other. Find the maximum number of cells that can be marked on a $100 \times 100$ board such that there are no two marked cells with a distance of 15 between them.

(I. Bogdanov)
Answer. $55^{2}=3025$ cells.

Solution. Divide the board into 9 squares $30 \times 30$, 6 rectangles $10 \times 30$, and one square $10 \times 10$ (see Fig. 5). In each $30 \times 30$ square, the cells are divided into $15^{2}$ groups of four such that the distance between any two cells in the same group is 15 (each group consists of cells with coordinates $(a, b)$, $(a, b+15)$, $(a+15, b)$, and $(a+15, b+15)$). Therefore, in any such group, no more than one cell can be marked, meaning the total number of marked cells in such a square does not exceed $15^{2}$.

![](https://cdn.mathpix.com/cropped/2024_05_06_ffccc7ae5b6e131f62bbg-6.jpg?height=444&width=456&top_left_y=626&top_left_x=238)

Fig. 5

![](https://cdn.mathpix.com/cropped/2024_05_06_ffccc7ae5b6e131f62bbg-6.jpg?height=513&width=521&top_left_y=595&top_left_x=739)

Fig. 6

Similarly, each $10 \times 30$ rectangle (with the longer horizontal side) is divided into pairs of cells, each pair being 15 units apart (with coordinates $(a, b)$ and $(a+15, b)$) - therefore, no more than $15 \cdot 10$ cells can be marked in such a rectangle. Finally, the $10 \times 10$ square has $10^{2}$ cells. In total, the number of marked cells does not exceed $9 \cdot 15^{2} + 6 \cdot 15 \cdot 10 + 10^{2} = (3 \cdot 15 + 10)^{2} = 55^{2}$.

An example with this number of marked cells is shown in Fig. 6.

Comment. Only the answer - 0 points.

Only the correct example of marked cells provided - 1 point.

Proved only that the total number of marked cells is no more than $55^{2} - 5$ points.