5. Determine the maximum number of queens that can be placed on a $2017 \times 2017$ chessboard so that each queen attacks at most one of the others.

(Bojan Bašić and PSC)
5. Denote $n=2017$. Suppose that we have placed $m>n$ queens. No row contains more than two queens, so there are at least $m-n$ rows with two queens, and hence at most $m-2(m-n)=2 n-m$ are alone in their rows. Similarly, at most $2 n-m$ queens are alone in their columns. On the other hand, every queen is alone in its row or column, which means that $m \leqslant 2(2 n-m)$. Thus $m \leqslant\left[\frac{4 n}{3}\right]=2689$.

Image A shows 8 queens placed on a $6 \times 6$ board under the problem condition. Before proceeding to the $2017 \times 2017$ board, consider the following arrangement:

- On a $335 \times 335$ board, one can place 335 queens so that they do not attack each other even if the diagonals are extended modulo 335. Indeed, it suffices to place queens on the squares $(x, y)$ with $1 \leqslant x, y \leqslant 335$ and $y \equiv 2 x(\bmod 335)$, as on image B. Then all the sums $x+y$ are different modulo 335 and so are the differences $x-y$, so no two queens are in the same row, column or extended diagonal.

A $-6 \times 6$ board

![](https://cdn.mathpix.com/cropped/2024_06_04_31a83bcaa45a5783e6aeg-09.jpg?height=314&width=306&top_left_y=1974&top_left_x=151)

B $-335 \times 335$ board

![](https://cdn.mathpix.com/cropped/2024_06_04_31a83bcaa45a5783e6aeg-09.jpg?height=416&width=416&top_left_y=1874&top_left_x=625)

![](https://cdn.mathpix.com/cropped/2024_06_04_31a83bcaa45a5783e6aeg-09.jpg?height=472&width=456&top_left_y=1841&top_left_x=1173)

Let us divide the $2017 \times 2017$ board into rectangles and squares with sides 335 , 6 and 1 , as on image $\mathrm{C}$. We arrange queens on the squares denoted $\mathrm{B}$ and $\mathrm{A}$ as shown on images B and $\mathrm{A}$, and put one more queen in the upper-right cell. Thus we have placed $8 \cdot 335+8+1=2689$ queens in total. It is easily verified that this arrangement fulfills the requirements.

Remark. The $n \times n$ board whose diagonals are extended modulo $n$ is known as a torus board. It is known that it is possible to place $n$ mutually non-attacking queens on a torus board $n \times n$ if and only if $n \equiv \pm 1(\bmod 6)$.