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 4 of 6: Partition into knight cycles

Previous step Next step

In plain words

The repeated labels describe four disjoint loops. Consecutive positions in each loop are exactly a forbidden knight jump apart.

\begin{array}{cccc}3&2&1&4\\1&4&3&2\\2&3&4&1\\4&1&2&3\end{array}

Detailed analysis

Partition the $20\times20$ board into $25$ disjoint $4\times4$ blocks. In each block, label the sites by the displayed array. The four sites carrying any fixed label form a cycle in which consecutive sites differ by $(1,2)$ or $(2,1)$ in their coordinates, hence consecutive sites are at distance $\sqrt{5}$ . The four labels therefore give four disjoint knight-jump cycles per block.