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 3 of 6: Amy secures the lower bound

Previous step Next step

In plain words

Amy keeps choosing a free site of the safe color; Ben can remove at most one such site between two of Amy's turns.

200\ \text{sites}\ \xrightarrow{\ \text{Amy/Ben turns}\ }\text{at least }100\ \text{red stones}

Detailed analysis

Amy restricts every red move to the $200$ sites with even coordinate sum. Every such move is legal by the previous step. Before Amy's $100$ th turn, Ben has made at most $99$ moves, so he cannot have occupied all $200$ safe sites; in general, after $r$ Amy moves and at most $r-1$ Ben moves, at least one safe site remains whenever $r\le100$ . Hence Amy can make at least $100$ red moves.