Bverov S.L.

On some cells of a $10 \times 10$ board, $k$ rooks were placed, and then all cells that are attacked by at least one rook (a rook attacks the cell it stands on as well) were marked. For what largest $k$ can it happen that after removing any rook from the board, at least one marked cell will no longer be under attack?
Evaluation. Let's consider the placement of $k$ rooks satisfying the condition. There are two possible cases.

1) In each column, there is at least one rook. Then the entire board is under attack, and a rook can be removed from any column that has at least two rooks. Therefore, in this case, there is exactly one rook in each column, and $k=10$.
2) There is an empty row and an empty column. Then the cell at their intersection is not under attack. Note that each rook is the only one either in its row or in its column (otherwise, it can be removed). For each rook, mark this row or this column. If no more than eight columns and no more than eight rows are marked, then the total number of rooks is no more than $8+8=16$. If, for definiteness, nine columns are marked, then there are a total of nine rooks (one in each of the nine columns, and by assumption, there are no rooks in the tenth column).

Thus, $k \leq 16$.

An example for 16 rooks is shown in the figure.

![](https://cdn.mathpix.com/cropped/2024_05_06_ed128c2d5b4d71db92ebg-06.jpg?height=766&width=832&top_left_y=29&top_left_x=613)

Send a comment