At most how many rooks can be placed on a $k \times n$ chessboard such that each one attacks exactly one other?
We can assume that $k \leq n$. If we place the rooks in the desired manner, then each rook can be uniquely assigned to the rook it attacks. Therefore, it is certain that only an even number of rooks can be placed in the desired manner. Let's call two rooks that attack each other a "pair," and the rows and columns of the chessboard collectively "strips." A pair occupies 3 strips, and no further rooks can be placed on these 3 strips.

On a $k \times n$ chessboard, $k+n$ strips are available, so at most $\left[\frac{k+n}{3}\right]$ pairs, or $2 \cdot\left[\frac{k+n}{3}\right]$ rooks, can be placed in the desired manner.

However, the number of pairs cannot be greater than either the number of horizontal or vertical strips. This, due to $k \leq n$, gives the upper estimate of $2k$.

If $n>2k$, then this latter estimate is smaller than the former, and furthermore, in this case, $2k$ rooks can be placed in the desired manner (Figure 1).

![](https://cdn.mathpix.com/cropped/2024_05_02_1673cc1afd46180db07bg-1.jpg?height=331&width=577&top_left_y=664&top_left_x=752)

# Figure 1

If $n \leq 2k$, then $2 \cdot\left[\frac{k+n}{3}\right] \leq 2k$. We will show that on a $k \times n$ chessboard, when $k \leq n \leq 2k$, $\left[\frac{k+n}{3}\right]$ suitable pairs can be placed.

We have seen that chessboards where one side is twice as long as the other can be filled with pairs placed parallel to the longer side. Let's try to divide our chessboard into such parts: (Figure 2)

![](https://cdn.mathpix.com/cropped/2024_05_02_1673cc1afd46180db07bg-1.jpg?height=591&width=422&top_left_y=1344&top_left_x=838)

Figure 2

According to the notation in the figure: $x+2y=n$, $y+2x=k$, from which

$$
x=\frac{2k-n}{3} \quad \text{ and } \quad y=\frac{2n-k}{3}.
$$

If these numbers are integers, then horizontally and vertically a total of $x+y=\frac{k+n}{3}$ pairs can be placed, which is exactly $\left[\frac{k+n}{3}\right]$, since the integer part is now an integer.

If $x$ or $y$ is not an integer, then we choose the sides of the horizontal rectangle to be $[x]$ and $2[x]$. The sides of the vertical rectangle are now $k-2[x]$ and $n-[x]$, and in this we need to place the missing $u=\left[\frac{k+n}{3}\right]-[x]$ pairs. This is certainly possible if the vertical rectangle contains a sub-rectangle with sides $u \times 2u$, i.e., if

$$
k-2[x] \geq u \quad \text{ and } \quad n-[x] \geq 2u.
$$

The first inequality, after substitution and rearrangement, takes the form

$$
\left[\frac{k+n}{3}\right]+\left[\frac{2k-n}{3}\right] \leq k.
$$

This is true because the sum of the numbers inside the integer parts is $k$. From the second inequality, since $n$ is an integer and thus $n+[x]=[n+x]$,

$$
2 \cdot\left[\frac{k+n}{3}\right] \leq n+\left[\frac{2k-n}{3}\right]=\left[2 \cdot \frac{k+n}{3}\right]
$$

follows. However, the inequality $2[t] \leq [2t]$ holds for any number.

In summary, if $n>2k$, then on a $k \times n$ chessboard, at most $2k$ rooks can be placed in the desired manner, and if $k \leq n \leq 2k$, then $2 \cdot\left[\frac{k+n}{3}\right]$ rooks can be placed in the desired manner.

Remark. Many have proven that $2k$ and $2 \cdot\left[\frac{k+n}{3}\right]$ are upper bounds - this is essentially evident from the solution to Exercise 2064 - but they did not examine whether these bounds are achievable.