第4問

サイトとは、平面上の点

(x,y)

で

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

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

\sqrt{5}

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

K

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

K

を求めよ。

ステップ 5/6: Ben のペアリング応手

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

ざっくり言うと

Amy が輪の1点を取ったら、Ben はその反対側の点を取る。残り2点は Amy にとって不適法なので、その輪から2個目の赤石は出ない。

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

詳しい解説

Ben は同じ巡回路で、Amy が新たに選んだ頂点の反対側の頂点を占める。その頂点はまだ空いている。なぜならこの巡回路で Ben が以前に応じたのは高々1回であり、巡回路同士は互いに素だからである。残りの2頂点は Amy の赤石からそれぞれ $\sqrt{5}$ の距離にあり、Amy は使えない。したがって各巡回路で赤石は高々1個、各 $4\times4$ ブロックで高々 $4$ 個である。