Determine the maximum number of queens that can be placed on a 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 . Suppose that queens are placed.
No row contains more than two queens, so at least rows contain two queens each, so that there are at most queens that are alone in their row. Similarly, at most queens are alone in their column.
On the other hand, every queen is alone in its row or in its column, so , from which .
Figure A shows a placement of 8 queens on a board in accordance with the requirement of the problem. Before constructing the example on the board, we will consider the following arrangement of queens:
- On a 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 , for which , as in Figure B. Indeed, then all sums are mutually distinct modulo 335, and likewise all differences , so no two queens are in the same row, column, or diagonal.
Let us divide the 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 queens. It is easily verified that such a placement satisfies the conditions of the problem.
