4. What is the largest number of rooks that can be placed on a $3 n \times 3 n$ chessboard such that each rook is attacked by at most one of the other rooks.
Solution. Let's assume that on a $3 n \times 3 n$ chessboard, several rooks are placed such that each of them is attacked by at most one of the other rooks. Let there be $2 x$ rooks that attack each other in pairs and $y$ rooks such that none of them attack any of the other rooks. Any two rooks that attack each other cover all fields on 3 lines (two horizontal and one vertical or two vertical and one horizontal). Each rook that does not attack any other rooks covers all fields on one horizontal and one vertical line. Therefore, all the placed rooks cover a total of $3 x + 2 y$ lines, some of which are horizontal and some are vertical. Since the total number of lines is $6 n$, we have $3 x + 2 y \leq 6 n$. The number of placed rooks is $2 x + y$, and it holds that

$$
2 x + y \leq \frac{2}{3}(3 x + 2 y) \leq 4 n
$$

For $n=3$, the diagram above shows how $4 n$ rooks can be placed on a $3 n \times 3 n$ board such that the conditions of the problem are satisfied. A similar example can be constructed for any natural number $n$.

## 4th Year