Maths Olympiad Prep

Library / /164 of 383

Combinatorics Difficulty 8.5 Shortlist Prove it IMO

Queenie and Horst play a game on a 20×2020 \times 20 chessboard. In the beginning the board is empty. In every turn, Horst places a black knight on an empty square in such a way that his new knight does not attack any previous knights. Then Queenie places a white queen on an empty square. The game gets finished when somebody cannot move.
Find the maximal positive KK such that, regardless of the strategy of Queenie, Horst can put at least KK knights on the board.

Solution

We show two strategies, one for Horst to place at least 100100 knights, and another strategy for Queenie that prevents Horst from putting more than 100100 knights on the board.

A strategy for Horst: Put knights only on black squares, until all black squares get occupied.

Colour the squares of the board black and white in the usual way, such that the white and black squares alternate, and let Horst put his knights on black squares as long as it is possible. Two knights on squares of the same colour never attack each other. The number of black squares is 202/2=20020^{2} / 2 = 200. The two players occupy the squares in turn, so Horst will surely find empty black squares in his first 100100 steps.

A strategy for Queenie: Group the squares into cycles of length 44, and after each step of Horst, occupy the opposite square in the same cycle.

Consider the squares of the board as vertices of a graph; let two squares be connected if two knights on those squares would attack each other. Notice that in a 4×44 \times 4 board the squares can be grouped into 44 cycles of length 44, as shown in Figure 1. Divide the board into parts of size 4×44 \times 4, and perform the same grouping in every part; this way we arrange the 400400 squares of the board into 100100 cycles (Figure 2).

Figure 1
Figure 1

Figure 2
Figure 2

Figure 3
Figure 3

The strategy of Queenie can be as follows: Whenever Horst puts a new knight to a certain square AA, which is part of some cycle ABCDAA-B-C-D-A, let Queenie put her queen on the opposite square CC in that cycle (Figure 3). From this point, Horst cannot put any knight on AA or CC because those squares are already occupied, neither on BB or DD because those squares are attacked by the knight standing on AA. Hence, Horst can put at most one knight on each cycle, that is at most 100100 knights in total.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.