第4問

サイトとは、平面上の点

(x,y)

で

x,y\in\{1,2,\ldots,20\}

を満たすものとする。はじめ、400個のサイトはすべて空いている。Amy と Ben は空いているサイトに交互に石を置き、Amy が先手である。Amy は、赤い石が置かれた任意の2サイト間の距離が

\sqrt{5}

にならないように赤石を置く。Ben は距離の制限なしに、空いている任意のサイトへ青石を置く。どちらかが石を置けなくなった時点で終了する。Ben の置き方によらず、Amy が少なくとも

K

個の赤石を置けることを保証できる最大の

K

を求めよ。

ステップ 4/6: ナイト巡回路に分割する

前のステップ次のステップ

ざっくり言うと

同じ数字の繰り返しが互いに素な4つの輪を表す。各輪で隣り合う位置は、ちょうど禁止されたナイト移動の距離にある。

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

詳しい解説

盤 $20\times20$ を互いに素な $25$ 個の $4\times4$ ブロックに分け、各ブロックを図の配列でラベル付けする。任意の固定したラベルを持つ4サイトは巡回路を作り、隣り合うサイトの座標差は $(1,2)$ または $(2,1)$ なので距離は $\sqrt{5}$ である。したがって各ブロックには互いに素なナイト巡回路が4つある。