Maths Olympiad Prep

Library / /27 of 87

Combinatorics Difficulty 5.9 AIME, harder Prove it Serbia

Determine the maximum number of queens that can be placed on a 2017×20172017 \times 2017 board, such that each queen is allowed to attack at most one of the remaining queens.
(Bojan Bašić and the committee)

Solution

Solution:

Let us denote n=2017n=2017. Suppose that m>nm>n queens are placed.

No row contains more than two queens, so at least mnm-n rows contain two queens each, so that there are at most m2(mn)=2nmm-2(m-n)=2 n-m queens that are alone in their row. Similarly, at most 2nm2 n-m queens are alone in their column.

On the other hand, every queen is alone in its row or in its column, so m2(2nm)m \leqslant 2(2 n-m), from which m[4n3]=2689m \leqslant\left[\frac{4 n}{3}\right]=2689.

Figure A shows a placement of 8 queens on a 6×66 \times 6 board in accordance with the requirement of the problem. Before constructing the example on the 2017×20172017 \times 2017 board, we will consider the following arrangement of queens:
- On a 335×335335 \times 335 board it is possible to place 335 queens that do not attack each other even if the diagonals are extended modulo 335. Indeed, it suffices to place queens on all squares (x,y),1x,y335(x, y), 1 \leqslant x, y \leqslant 335, for which y2x(mod335)y \equiv 2 x(\bmod 335), as in Figure B. Indeed, then all sums x+yx+y are mutually distinct modulo 335, and likewise all differences xyx-y, so no two queens are in the same row, column, or diagonal.

Let us divide the 2017×20172017 \times 2017 board into rectangles and squares with sides 335, 6, and 1, as in Figure C. We will fill in the squares marked B and A successively as in Figures B and A, and we will place one more queen on the upper right square of the board. In this way we have placed a total of 8335+8+1=26898 \cdot 335+8+1=2689 queens. It is easily verified that such a placement satisfies the conditions of the problem.

Figure 1

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from sr; metadata (topic, difficulty) added by this project.