5. What is the maximum number of rooks that can be placed on the cells of a $300 \times 300$ board so that each rook attacks no more than one other rook? (A rook attacks all cells it can reach according to chess rules, without passing through other pieces.)

#
# Answer: 400

First solution. We will prove that no more than 400 rooks can be placed on the board. In each row or column, there are no more than two rooks; otherwise, the rook that is not at the edge will attack at least two other rooks. Suppose there are $k$ columns with two rooks each. Consider one such pair. They attack each other, so there are no rooks in the rows where they are located. Thus, rooks can only be in $300-2k$ rows. Since there are no more than two rooks in each of these rows, the total number of rooks is no more than $2(300-2k) + 2k = 600 - 2k$. On the other hand, in $k$ columns, there are two rooks each, and in the remaining $300-k$ columns, there is no more than one rook, so the total number of rooks is no more than $(300-k) + 2k = 300 + k$. Therefore, the total number of rooks is no more than $\frac{1}{3}((600-2k) + 2(300+k)) = 400$.

Next, we will show how to place 400 rooks. On a $3 \times 3$ board, 4 rooks can be placed as shown in the figure, and then 100 such squares can be placed along the diagonal.

![](https://cdn.mathpix.com/cropped/2024_05_06_52ba2bd370bb2f80da76g-07.jpg?height=133&width=124&top_left_y=2261&top_left_x=1520)

Second solution. On the board, there can be rooks that do not attack any other rooks, as well as pairs of rooks that attack each other. Let there be $k$ single rooks and $n$ pairs of rooks that attack each other. Then the total number of rooks on the board is $k + 2n$. We will count the total number of occupied rows and columns (for convenience, we will call them lines). Each single rook occupies its own row and its own column, i.e., two lines. Each pair of rooks occupies three lines. Therefore, the total number of lines occupied is $2k + 3n$. Thus, $2k + 3n \leq 600$. Therefore, $k + 2n = \frac{2}{3}(2k + 3n) - \frac{k}{3} \leq \frac{2}{3}(2k + 3n) \leq \frac{2}{3} \cdot 600 = 400$.

The example of placement is the same as in the first solution.