2018 IMO #C2 (#4)

A site is any point $(x, y)$ in the plane such that $x$ and $y$ are both positive integers less than or equal to 20. Initially, each of the 400 sites is unoccupied. Amy and Ben take turns placing stones with Amy going first. On her turn, Amy places a new red stone on an unoccupied site such that the distance between any two sites occupied by red stones is not equal to $\sqrt{5}$. On his turn, Ben places a new blue stone on any unoccupied site. (A site occupied by a blue stone is allowed to be at any distance from any other occupied site.) They stop as soon as a player cannot place a stone. Find the greatest $K$ such that Amy can ensure that she places at least $K$ red stones, no matter how Ben places his blue stones.

The answer is $K=100$. 

Remember that the $\sqrt{5}$ distance between two sites can only be achieved by a knight's move on a chessboard.

First, we show Amy can place at least 100 stones. Then we would show that Ben can always prevent Amy from occupying more than 100 sites.

Think of the board as a white-and-black chessboard. Then Amy decides to play on only 200 black squares - because that way all the sites at a knight's move away will fall on one of the white squares. In this way, she can guarantee half the black squares, or 100 stones. 

Next, we will show that Ben can prevent Amy from placing more than 100 stones. Divide the entire grid into $4 \times 4$ squares, and label each site in the square as follows: 

$$1 \qquad 2 \qquad 3 \qquad 4$$

$$3 \qquad 4 \qquad 1 \qquad 2$$

$$2 \qquad 1 \qquad 4 \qquad 3$$

$$4 \qquad 3 \qquad 2 \qquad 1$$. 

The significance of this is that if Amy places a red stone at some spot labelled 1, then she can place another red stone only at one of the remaining 1's in this square. The same would be true for the spot labelled 2, 3, and 4. Now, we make Ben always capture that single spot, so as to make sure that Ben always captures a spot that Amy could have used; not the one that are already prevented by the constraint of $\sqrt{5}$. Hence Amy can place at most in $\frac{1}{4}$ of the sites, which is $400 \cdot \frac{1}{4}=100$, as desired. $\square$