IMO 2018 P4

I was baffled by this for quite a while, although as P4 it's supposed to be pretty simple! Anyways, just like some combinatoric problems it is very hard until you see the trick, which then becomes easy.

This time I conceived the key trick while having routine dental cleaning.

================================================

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.

================================================

Solution:

\(K=100\).

Amy can always get \(100\) cells. Embed the cells in a \(20\times 20\) checker board. By taking only black cells, she is guaranteed that no two cells taken by her are \(\sqrt{5}\) units apart. There are \(200\) black cells so Amy can always get at least \(100\) of them.

Ben can always prevent Amy from taking more than \(100\) cells. Partition the cells into disjoint \(4\times 4\) blocks, and further partition each block into \(4\) groups as

ABCD
CDAB
BADC
DCBA

Within each group Amy cannot take more than one cell if Ben plays optimally.