第4問

サイトとは、平面上の点

(x,y)

で

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

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

\sqrt{5}

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

K

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

K

を求めよ。

ステップ 1/6: 目標値を定める

ざっくり言うと

Amy が保証できる下界と Ben が強制できる上界をそれぞれ示し、両者が一致すれば答えが定まる。

K=100\ \text{is the target value}

詳しい解説

保証できる最大数が $K=100$ であることを示す。下界には市松模様の戦略を、上界には $4\times4$ ブロック内で独立に行うペアリング戦略を用いる。