MathLabs

第4题

称平面上的点 (x,y)(x,y) 为一个位置，其中 x,y∈{1,2,…,20}x,y\in\{1,2,\ldots,20\}。开始时，400 个位置都未被占用。Amy 与 Ben 轮流在未占用的位置放置棋子，Amy 先手。Amy 放置红棋子时，任意两个红棋子所在位置的距离都不能等于 5\sqrt{5}。Ben 可以在任意未占用的位置放置蓝棋子，不受距离限制。当某一方不能放置棋子时，游戏立即结束。求最大的 KK，使得无论 Ben 如何放置，Amy 都能保证至少放置 KK 个红棋子。
第 3/6 步：Amy 保证下界
上一步下一步
通俗地说

Amy 始终选择安全颜色中的空位；在 Amy 的两次落子之间，Ben 至多占去一个这种位置。

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 个红棋子。