IMO 2018 · Problem 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.

Official text of the problem. Official problem paper (PDF)

Answer

\[ \boxed{K=100}. \]

Solution

We first show that Amy can guarantee \(100\) red stones.

Call a site \((x,y)\) white if \(x+y\) is even. There are exactly \(200\) white sites. Two sites at distance \(\sqrt5\) have coordinate differences whose absolute values are \(1\) and \(2\), so exactly one of them is white. Consequently, Amy may legally place all her stones on white sites.

Before Amy’s \(k\)-th turn, at most \(2(k-1)\) white sites have been occupied. For \(k\le100\), this is at most \(198\), so an unoccupied white site remains. Ben cannot run out of unoccupied sites during these turns either, since fewer than \(400\) sites are occupied. Thus Amy can place at least \(100\) red stones.

We now give Ben a strategy ensuring that Amy places at most \(100\) red stones.

Partition the board into \(25\) blocks of \(4\times4\) sites: \[ B_{i,j}=\{(4i+a,4j+b):1\le a,b\le4\}, \qquad 0\le i,j\le4. \] Within each block, use local coordinates \((a,b)\), and partition its sites into the following four ordered quadruples: \[ \begin{aligned} Q_1&=((1,1),(2,3),(4,4),(3,2)),\\ Q_2&=((1,4),(2,2),(4,1),(3,3)),\\ Q_3&=((1,2),(3,1),(4,3),(2,4)),\\ Q_4&=((1,3),(2,1),(4,2),(3,4)). \end{aligned} \] These lists contain each of the \(16\) local sites exactly once. In every quadruple, consecutive sites, including the last and first, have coordinate differences with absolute values \(1\) and \(2\). Hence consecutive sites are at distance \(\sqrt5\).

We have therefore partitioned the board into \(100\) quadruples, each arranged cyclically so that neighboring sites are at distance \(\sqrt5\). Call two sites opposite if they are two positions apart in their quadruple.

Ben’s strategy is this: whenever Amy places a red stone, he places a blue stone on the opposite site of the same quadruple.

To verify that this strategy always works, maintain the following property after each of Ben’s turns: every quadruple is either completely empty, or contains one red stone and a blue stone opposite it. In the latter case, both remaining sites are at distance \(\sqrt5\) from the red stone, so Amy cannot play there.

The property holds initially. If it holds before Amy’s next move, her move must be in an empty quadruple. Its opposite site is therefore unoccupied, so Ben’s prescribed response is legal and preserves the property.

Thus every red stone Amy places uses a previously empty quadruple, and she can never place a second red stone in that quadruple. There are only \(100\) quadruples, so Ben ensures that she places at most \(100\) red stones.

Combining the two strategies gives \(K=100\).

The solution was checked against the official IMO shortlist solutions.