MathLabs

第4問

サイトとは、平面上の点 (x,y)(x,y) で x,y∈{1,2,…,20}x,y\in\{1,2,\ldots,20\} を満たすものとする。はじめ、400個のサイトはすべて空いている。Amy と Ben は空いているサイトに交互に石を置き、Amy が先手である。Amy は、赤い石が置かれた任意の2サイト間の距離が 5\sqrt{5} にならないように赤石を置く。Ben は距離の制限なしに、空いている任意のサイトへ青石を置く。どちらかが石を置けなくなった時点で終了する。Ben の置き方によらず、Amy が少なくとも KK 個の赤石を置けることを保証できる最大の KK を求めよ。
ステップ 3/6: Amy が下界を確保する
前のステップ次のステップ
ざっくり言うと

Amy は安全な色の空きサイトを選び続ける。Amy の2回の手の間に Ben が取り除ける同色サイトは高々1個である。

200 sites → Amy/Ben turns at least 100 red stones200\ \text{sites}\ \xrightarrow{\ \text{Amy/Ben turns}\ }\text{at least }100\ \text{red stones}
詳しい解説

Amy は赤石を座標和が偶数の 200200 サイトに限る。前段階によりそれぞれの手は合法である。Amy の 100100 回目の手の前には Ben の手は高々 9999 回なので、200200 個の安全なサイトをすべて占めることはできない。一般に Amy が rr 回、Ben が高々 r−1r-1 回打った後は r≤100r\le100 なら安全なサイトが残る。よって Amy は少なくとも 100100 個の赤石を置ける。