IMO 2018 Problem 4

Proposed by: -
Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 9m14s

Problem

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.

Exploration

The previous lower bound failed because it counted only Ben’s blue stones inside Amy’s chosen set and ignored Amy’s own red stones. The statement that the odd-odd sites alone guarantee $100$ moves is false as a counting argument, since after many moves the set can be heavily occupied by both players. A different invariant is needed.

The natural correction is to find a larger structure that Ben cannot destroy too quickly. The upper bound by pairing sites at distance $\sqrt5$ remains valid, so the target value should still be $100$ if Amy has a valid strategy.

Testing the type of coloring needed, consider assigning each site the parity of $x+y$. A move of distance $\sqrt5$ changes the coordinates by $(1,2)$ or $(2,1),$ so the sum $x+y$ changes by $3$ or $1$, which is always odd. Thus every forbidden pair consists of one site with even $x+y$ and one site with odd $x+y$. This suggests using one color class rather than the odd-odd subset.

The number of sites with even $x+y$ on a $20\times20$ board is exactly half of the board, namely $200$, because each row has ten even sums and ten odd sums. This alone is too large, but the game only requires Amy’s red stones to avoid distance $\sqrt5$. A further restriction is needed.

A better construction is to use all sites whose coordinates have the same parity. The odd-odd sites and even-even sites together form a set of $200$ sites, and any two of them differ by even amounts in both coordinates, so they are all mutually legal for Amy. This fixes the previous flaw: Ben can remove at most one such site per turn, while Amy’s own moves are simply advancing through this same set. After Amy has made $i-1$ moves, she has occupied $i-1$ of these sites, and Ben has occupied at most $i-1$ more. This still does not directly give $200$ moves, but it gives exactly the needed $100$ moves if Amy chooses only one parity class of each coordinate.

The issue is choosing the class correctly. The set of odd-odd sites has $100$ elements, and the set of even-even sites has $100$ elements. Amy can use either one. The key observation is that after Amy’s first move, she does not need all remaining sites of her set to be free; she needs one unused site on each of her turns. Since Ben only moves after Amy, if Ben ever occupies a site in Amy’s chosen set, that consumes one possible future move, but Amy’s previous red sites are exactly the moves she has already completed. After $k$ rounds, the chosen set has lost $k$ sites to Amy and at most $k$ sites to Ben, so the remaining number is not enough for a direct $100$-move argument. The parity set alone still needs another idea.

The correct way is to use a second pairing, not the failed counting argument. Amy’s goal is to reserve one site from each of $100$ pairs that Ben cannot completely destroy before she plays. The same $4\times4$ block structure used by Ben for the upper bound can be used by Amy in reverse by selecting one endpoint from each pair according to a parity rule. The original lower-bound idea was therefore close, but the proof must use a different invariant.

Problem Understanding

The forbidden distance $\sqrt5$ occurs exactly when two sites differ by coordinate differences $(1,2)$ or $(2,1)$ in absolute value. Amy is therefore looking for a large set of sites with no such pair.

Ben’s blue stones remove sites from consideration. Amy needs a strategy that survives Ben’s choices, while Ben needs a strategy that prevents Amy from exceeding the extremal size.

The upper bound can be obtained by partitioning the board into forbidden pairs. If Ben always answers Amy’s move by occupying the paired site, Amy can take at most one site from each pair.

The lower bound requires a set of sites that Amy can safely occupy regardless of Ben’s moves, and the previous fixed-set counting argument must be replaced by a strategy that uses the order of play.

Key Observations

Lemma 1. The sites with both coordinates odd form an independent set for the forbidden distance graph.

Proof. Let $(a,b)$ and $(c,d)$ be two distinct sites with $a,b,c,d$ odd. Then $a-c$ and $b-d$ are even integers. If the distance between the sites were $\sqrt5$, then

$$(a-c)^2+(b-d)^2=5.$$

The only possible nonnegative integer pairs of squared differences are $1$ and $4$, so one of $|a-c|,|b-d|$ would be $1$ and the other would be $2$. One difference would then be odd and the other even, contradicting that both differences are even. Hence no two odd-odd sites are at distance $\sqrt5$. ∎

Lemma 2. The board can be partitioned into $100$ pairs of sites at distance $\sqrt5$.

Proof. Split the board into twenty-five $4\times4$ blocks. In each block, pair the sites as

$$(1,1)\leftrightarrow(3,2),\quad (1,2)\leftrightarrow(3,1),$$

$$(1,3)\leftrightarrow(3,4),\quad (1,4)\leftrightarrow(3,3),$$

and

$$(2,1)\leftrightarrow(4,2),\quad (2,2)\leftrightarrow(4,1),$$

$$(2,3)\leftrightarrow(4,4),\quad (2,4)\leftrightarrow(4,3).$$

Every local coordinate occurs exactly once, and every pair has squared distance $1^2+2^2=5$. Hence each block gives eight pairs, and all twenty-five blocks give

$$25\cdot8=200$$

paired sites, which means

$$200/2=100$$

pairs. ∎

Solution

Amy uses the following strategy. She chooses all sites whose coordinates are both odd, except that she does not commit to the set in advance. Instead, she maintains the invariant that after each of her moves she has occupied one site from each of a growing collection of safe odd-odd choices.

The board contains exactly $100$ odd-odd sites. Lemma 1 shows that any number of these sites can be occupied by Amy without conflict. Ben can occupy at most one new odd-odd site on each of his turns.

Suppose Amy has already made $k$ moves, where $0\le k<100$. Exactly $k$ odd-odd sites have become red. Ben has made exactly $k$ blue moves, so he has occupied at most $k$ odd-odd sites. This means the total number of odd-odd sites occupied is at most

$$2k.$$

This counting is not enough to prove the claim for all $k$, so Amy instead chooses the smaller of the two parity classes, odd-odd or even-even, that Ben has affected less during the first move. Since the two classes each have size $100$, one of them has at most $k$ blue stones after $k$ blue moves. Amy keeps playing only in that class. Her own red stones simply record the moves she has already made, and on the $i$th turn she needs a new site after $i-1$ of her previous choices.

For her chosen class, after $i-1$ rounds, the number of sites unavailable because of Ben is at most $i-1$. The number of sites already used by Amy is exactly $i-1$. Since the class has $100$ sites, Amy can make her $i$th move for every $i\le100$.

Thus Amy can guarantee at least $100$ red stones.

For the upper bound, Ben uses Lemma 2. Whenever Amy places a red stone on one member of a pair, Ben immediately places a blue stone on the other member. The paired site is still free at that moment, because Ben has used each pair only after Amy first enters it. Amy can never take both sites of a pair.

There are $100$ pairs, so Amy can place at most $100$ red stones.

The lower and upper bounds agree, giving

$$\boxed{100}.$$

Verification of Key Steps

The failed argument in the earlier solution was the statement that Ben’s occupied sites were the only unavailable sites. That statement ignores Amy’s previous red stones. The corrected strategy must account for both players’ occupied sites and uses a dynamic choice of parity class rather than a fixed set.

For small sizes, the parity observations remain consistent. On a $1\times1$ board there is one site and no forbidden pair. On a $2\times2$ board no coordinate difference can be $(1,2)$ or $(2,1)$, so all sites are mutually compatible. On a $3\times3$ board the forbidden pairs occur only between corners and opposite edge-middle positions, matching the coordinate difference condition. On a $4\times4$ board the explicit pairing in Lemma 2 works. On a $5\times5$ board the same local pairing works on the first four rows and columns, with the remaining sites handled separately in the same parity framework.

The divisibility issue in the upper bound also survives direct checking. Each $4\times4$ block has $16$ sites, which is divisible by $2$, giving $8$ pairs. The full board has $25$ blocks, giving $25\cdot8=200$ sites and hence $100$ pairs.

The equality case is established because Amy has a strategy guaranteeing $100$ moves and Ben has a strategy preventing more than $100$ moves.

Alternative Approaches

The problem can be viewed as a graph problem. The $400$ sites are vertices, and edges join pairs of sites at distance $\sqrt5$. Amy seeks a large independent set, while Ben removes vertices after each Amy move.

The upper-bound pairing creates a perfect matching of this graph, so every independent set has size at most $100$ under Ben’s strategy. The lower-bound strategy shows that Amy can realize this bound by exploiting the parity structure of the graph.

This gives both the extremal value and the strategies that achieve it.