What is the maximum number of rooks that can be placed on a $4 \times 4$ chessboard so that each one attacks exactly one other?

What is the answer on an $8 \times 8$ chessboard?
If we place the rooks in the desired manner, then each rook can be uniquely assigned to the rook it attacks. Thus, it is certain that in the desired manner, only an even number of rooks can be placed. Let's call two rooks that attack each other a "pair," and the rows and columns of the chessboard collectively as "bands." A pair occupies 3 bands, and no further rooks can be placed on these 3 bands.

On a $4 \times 4$ chessboard, there are $2 \cdot 4 = 8$ bands available, so at most $\left[\begin{array}{l}8 \\ 3\end{array}\right] = 2$ pairs - that is, 4 rooks - can be placed in the desired manner. Such an arrangement is shown in Figure 1.

![](https://cdn.mathpix.com/cropped/2024_05_02_0fa540957c3fa7e8d1acg-1.jpg?height=544&width=480&top_left_y=468&top_left_x=801)

Figure 1

On an $8 \times 8$ chessboard, there are 16 bands, so at most $\left[\frac{16}{3}\right] = 5$ pairs - that is, 10 rooks - can be placed, and such an arrangement is shown in Figure 2.

![](https://cdn.mathpix.com/cropped/2024_05_02_0fa540957c3fa7e8d1acg-1.jpg?height=770&width=764&top_left_y=1182&top_left_x=667)

Figure 2

Note. It can be shown that on an $n \times n$ chessboard, $2 \cdot \left[\frac{2n}{3}\right]$ rooks can be placed in the desired manner, but no more. More generally, on a $k \times n$ chessboard, for $k \leq n \leq 2k$, the maximum number of rooks that can be placed is $2 \cdot \left[\frac{k+n}{3}\right]$, and for $n \geq 2k$, the maximum number of rooks is $2k$.