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 5 of 6: Ben's pairing response

Previous step Next step

In plain words

When Amy takes one point of a loop, Ben takes the point opposite it. The other two points are illegal for Amy, so that loop can never yield a second red stone.

\text{one red stone per cycle}\quad\Longrightarrow\quad4\text{ red stones per }4\times4\text{ block}

Detailed analysis

Ben responds within the same cycle by occupying the vertex opposite Amy's newly chosen vertex. That opposite vertex is still free because Ben has previously responded in this cycle at most once, and the cycles are disjoint. The two remaining vertices are each at distance $\sqrt{5}$ from Amy's red stone, so Amy cannot use them. Thus Amy places at most one red stone in each cycle, hence at most $4$ red stones in each $4\times4$ block.