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 2 of 6: Choose one checkerboard color

Previous step Next step

In plain words

Coloring the board like a chessboard separates every forbidden knight jump: a knight always changes color.

\#\{(x,y):x+y\equiv0\pmod 2\}=200

Detailed analysis

There are $200$ sites with $x+y$ even. If two lattice sites are at distance $\sqrt{5}$ , their coordinate differences have absolute values $1$ and $2$ in some order, so their coordinate-sum parities are opposite. Thus no two sites with $x+y$ even are at the forbidden distance.