Problem 4

A site is any point

(x,y)

in the plane for which

x,y\in\{1,2,\ldots,20\}

. Initially all 400 sites are unoccupied. Amy and Ben take turns placing stones on unoccupied sites, with Amy going first. Amy places a red stone only if the distance between any two sites occupied by red stones is not equal to

\sqrt{5}

. Ben places a blue stone on any unoccupied site, without any distance restriction. 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, regardless of how Ben plays.

Step 1 of 6: Set the target

Previous step Next step

In plain words

We prove a lower bound that Amy can force and an upper bound that Ben can enforce; matching bounds determine the answer.

K=100\ \text{is the target value}

Detailed analysis

We will prove that the greatest guaranteed number is $K=100$ . The lower bound is a checkerboard strategy, while the upper bound is a pairing strategy applied independently inside $4\times4$ blocks.