Kozhevnikov P.A.

What is the minimum number of cells that need to be marked on a $15 \times 15$ board so that a bishop, from any cell on the board, attacks no fewer than two marked cells? (The bishop also attacks the cell it stands on.)

#
It is more convenient to solve the problem in general: we will show that on a board of size $(2 n+1) \times(2 n+1)(n>1)$, the answer is $4 n$. (The diagram corresponds to the case $n=3$.)

Example. Let's mark the cells along the perimeter of a rectangle $(2 n-1) \times 3$, as shown in the diagram. In this case, on the long diagonals (consisting of more than $n+1$ cells), two cells are marked. Only four cells of the board (they are shaded in the diagram) do not lie on the long diagonals, but the required condition is still satisfied for them.

![](https://cdn.mathpix.com/cropped/2024_05_06_afad11de590b368f242eg-43.jpg?height=526&width=517&top_left_y=0&top_left_x=776)

Estimate. Place $8 n$ bishops in all the cells along the perimeter of the board. In this case, each cell of the board is attacked by no more than four bishops. Since each bishop must attack at least two marked cells, it is necessary to mark at least $8 n \cdot 2: 4=4 n$ cells.

## Answer

28 cells.