第4問

サイトとは、平面上の点

(x,y)

で

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

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

\sqrt{5}

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

K

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

K

を求めよ。

ステップ 6/6: 上下界を一致させる

ざっくり言うと

ブロックは25個あり、Ben は各ブロックで赤石を4個までに抑える。これは Amy の市松模様による保証とちょうど一致する。

25\cdot4=100\quad\Longrightarrow\quad K\le100\quad\text{and hence}\quad K=100

詳しい解説

Ben の戦略により盤全体の赤石は高々 $25\cdot4=100$ 個なので、Amy は $100$ 個を超えて保証できない。一方、市松模様の戦略は少なくとも $100$ 個を保証する。したがって最大の保証値は $K=100$ である。