第4問

サイトとは、平面上の点

(x,y)

で

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

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

\sqrt{5}

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

K

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

K

を求めよ。

ステップ 2/6: 市松模様の一色を選ぶ

ざっくり言うと

盤を市松模様に塗ると、禁止されるナイト移動は必ず色を変えるので、同色のサイトは安全である。

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

詳しい解説

$200$ 個のサイトは $x+y$ が偶数である。格子点間の距離が $\sqrt{5}$ なら、座標差の絶対値は順序を除いて $1$ と $2$ であるから、座標和の偶奇は反対になる。したがって $x+y$ が偶数のサイト同士は禁じられた距離にない。