IMO Hk TST, 1997

The smallest possible value of $r$ is $2n$ if $n$ is even, and is $2n + 1$ if $n$ is odd.

Case 1. $n = 2k$ is even
Let $(i, j)$ be the cell in row $i$ and column $j$. Consider the following $2n$ diagonals:
$$\begin{aligned} \{(i, j) : i + j = m\} & \text{ for } m = 2, 3, \dots, k + 1, \\ \{(i, j) : j - i = m\} & \text{ for } m = k, k + 1, \dots, 2k - 1, \\ \{(i, j) : i - j = m\} & \text{ for } m = k, k + 1, \dots, 2k - 1, \\ \{(i, j) : i + j = m\} & \text{ for } m = 3k + 1, 3k + 2, \dots, 4k. \end{aligned}$$

Obviously, these diagonals are disjoint. Therefore, one chess piece is needed for each diagonal, and so $r \geq 2n$.

Now, we put $2n$ chess pieces in the following cells:
- $(1, j)$ for $j = 1, 2, \dots, k$,
- $(i, n)$ for $i = 1, 2, \dots, k$,
- $(i, 1)$ for $i = k + 1, k + 2, \dots, 2k$,
- $(n, j)$ for $j = k + 1, k + 2, \dots, 2k$.

Then we see that each row, each column and each diagonal consists of a chess piece. This proves $r = 2n$ when $n$ is even.

Case 2. $n = 2k + 1$ is odd
Consider the following $2n + 2$ diagonals:
$$\begin{aligned} \{(i,j) : i + j = m\} & \quad \text{for } m = 2, 3, \dots, k + 2, \\ \{(i,j) : j - i = m\} & \quad \text{for } m = k, k + 1, \dots, 2k, \\ \{(i,j) : i - j = m\} & \quad \text{for } m = k, k + 1, \dots, 2k, \\ \{(i,j) : i + j = m\} & \quad \text{for } m = 3k + 2, 3k + 3, \dots, 4k + 2. \end{aligned}$$

Only 4 pairs of these diagonals are not disjoint. We call these $C, D, I, J$-diagonals respectively, as labelled in the above example. One chess piece is needed for each of those $4k = 2n-2$ diagonals other than the $C, D, I, J$-diagonals.

If $r \le 2n$, then we can put at most 2 chess pieces in the $C, D, I, J$-diagonals. By the pigeonhole principle, one chess piece must occupy at least two such diagonals. WLOG assume there is a chess piece in $(1, k+1)$ occupying the $C, D$-diagonals. In order to occupy the $I, J$-diagonals simultaneously, there must be another chess piece in $(2k+1, k+1)$. But then there is no chess piece in row $k+1$. This is a contradiction. Thus, we have $r \ge 2n+1$.

Now, we put $2n + 1$ chess pieces in the following cells:
$$\begin{aligned} (1, j) & \quad \text{for } j = 1, 2, \dots, k + 1, \\ (i, n) & \quad \text{for } i = 1, 2, \dots, k, \\ (i, 1) & \quad \text{for } i = k + 2, k + 3, \dots, 2k + 1, \\ (n, j) & \quad \text{for } j = k + 1, k + 2, \dots, 2k + 1, \\ (k + 1, k + 1) & \end{aligned}$$

Then we see that each row, each column and each diagonal consists of a chess piece. This proves $r = 2n + 1$ when $n$ is odd.