Bervov S.l.

In some cells of a $10 \times 10$ board, $k$ rooks were placed, and then all cells that are attacked by at least one rook were marked (it is assumed that a rook attacks the cell it stands on). 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?
Let's consider the placement of $k$ rooks satisfying the condition. There are two possible cases.

1. Suppose there is at least one rook in each column. 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 \leq 10$. Similarly, if there is a rook in each row, then $k \leq 10$ as well.
2. Now suppose 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 in its row or its column (otherwise, it can be removed, and its row and column will remain under attack). For each rook, mark this row or column. If no more than 8 columns and no more than 8 rows are marked, then the total number of rooks is no more than $8+8=16$. If, for definiteness, 9 columns are marked, then there are a total of 9 rooks (one in each of the 9 columns, and by assumption, there are no rooks in the 10th column).

In all cases, we have $k \leq 16$. An example for 16 rooks is shown in the figure; for each rook, an arrow indicates the cell that will remain not under attack if that rook is removed.

Submit a comment