A chessboard is an $8 \times 8$ square where the squares are arranged in 8 rows and 8 columns.

![](https://cdn.mathpix.com/cropped/2024_05_01_e988dd467f3d6c2bf99fg-25.jpg?height=558&width=568&top_left_y=482&top_left_x=826)

A rook on a chessboard attacks all pieces that are in its row or column. Knowing this, determine:

a) What is the maximum number of rooks that can be placed on a chessboard so that no two attack each other?

b) What is the maximum number of rooks that can be placed on a chessboard so that each rook is threatened by at most one of the other rooks?
Solution

a) Below, we have an example with 8 towers, none of which are attacking each other.

![](https://cdn.mathpix.com/cropped/2024_05_01_e988dd467f3d6c2bf99fg-25.jpg?height=568&width=574&top_left_y=1778&top_left_x=818)

If we place 9 or more towers, since there are only 8 rows, there will be two in the same row, and one can attack the other. Therefore, the maximum number is 8.
b) Below, we have an example with 10 towers, each of which is attacked by at most one other tower.

![](https://cdn.mathpix.com/cropped/2024_05_01_e988dd467f3d6c2bf99fg-26.jpg?height=569&width=565&top_left_y=440&top_left_x=627)

Now we need to show that if we place 11 or more towers, there will be a tower threatened by at least two others. Consider a distribution of towers where each is threatened by at most one other. We can classify them into two groups: those that are not threatened by other towers, called solitary towers, and those that are threatened by exactly one other tower, called towers with enemies. For each solitary tower, we can place a label on its row and column. This uses exactly two labels. For each tower that is threatened by exactly one other, we can place a label on the rows and columns that contain it and its enemy. This uses exactly three labels in this case. If \( x \) is the number of solitary towers and \( 2y \) is the number of towers with enemies, where \( y \) is the number of pairs of enemy towers, then the number of labels used is \( 2x + 3y \). Additionally, since each row and column, totaling 16, received only one label, we have:

\[
\begin{aligned}
16 & \geq 2x + 3y \\
32 & \geq 4x + 6y \\
& \geq 3x + 6y
\end{aligned}
\]

Thus, \( 32 / 3 \geq x + 2y \). Since the number of towers, given by \( x + 2y \), is an integer and \( 32 / 3 < 11 \), it follows that there can be at most 10 towers on the board satisfying the conditions of the second item.