3. Determine the largest natural number $k$ for which it is possible to place $k$ rooks and $k$ bishops on an $8 \times 8$ chessboard such that no piece threatens another. (A bishop threatens any square on the same diagonal, and a rook threatens any square on the same row or column.)

(Josef Tkadlec)
Solution. Consider any valid placement of $k$ rooks and $k$ archers. We will prove that the inequality $k \leqq 5$ holds.

If a rook is placed in any row (or column) of the chessboard, it must be the only piece in that row (or column). Therefore, for the number $k$ of placed rooks, it must be true that $k \leqq 8$, and additionally, a total of $8-k$ rows and $8-k$ columns of the chessboard are not occupied by rooks. The $k$ archers can then stand on any of the $(8-k)^{2}$ squares where these rows and columns intersect. Therefore, the inequality

$$
k \leqq (8-k)^{2}
$$

must hold. From this, it follows that $k \leqq 5$, because the derived inequality does not hold for any $k \in \{6,7,8\}$, as can be easily verified by substitution.

As we can see from the following figure, 5 rooks and 5 archers can be placed on the chessboard in such a way that they do not threaten each other, so the largest possible $k$ with the given property is $k=5$.

![](https://cdn.mathpix.com/cropped/2024_04_17_dfff014c37a064e0cb05g-6.jpg?height=392&width=397&top_left_y=1226&top_left_x=832)

Fig. 2

Note. The derivation of the inequality $k \leqq 5$ can be presented more concisely as follows: first, we rule out the value $k=6$ (6 archers would have to stand on 4 squares, which lie in two rows and two columns not occupied by 6 rooks), and then we observe that if there were a valid placement for $k>6$, removing any $k-6$ rooks and $k-6$ archers would yield a valid placement for $k=6$.

For a complete solution, award 6 points. Of these, 1 point for ruling out the possibilities $k>6$ and 2 points for ruling out the possibility $k=6$. Finally, award 3 points for constructing a correct example of a valid placement for $k=5$. Do not award additional points for stating that no more rooks can be added to the found example for $k=5$—a complete solution to the problem would require testing all valid placements for $k=5$. If a correct example of a valid placement is given only for $k=4$, award 1 point.