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 6 of 6: Match the bounds

Previous step Next step

In plain words

There are 25 blocks and Ben limits Amy to four red stones in each, exactly matching Amy's checkerboard guarantee.

25\cdot4=100\quad\Longrightarrow\quad K\le100\quad\text{and hence}\quad K=100

Detailed analysis

Ben's strategy gives at most $25\cdot4=100$ red stones over the whole board, so Amy cannot guarantee more than $100$ . The checkerboard strategy already guarantees at least $100$ . Therefore the greatest possible guarantee is $K=100$ .