第4题

称平面上的点

(x,y)

为一个位置，其中

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

。开始时，400 个位置都未被占用。Amy 与 Ben 轮流在未占用的位置放置棋子，Amy 先手。Amy 放置红棋子时，任意两个红棋子所在位置的距离都不能等于

\sqrt{5}

。Ben 可以在任意未占用的位置放置蓝棋子，不受距离限制。当某一方不能放置棋子时，游戏立即结束。求最大的

K

，使得无论 Ben 如何放置，Amy 都能保证至少放置

K

个红棋子。

第 4/6 步：分成马步循环

上一步下一步

通俗地说

重复出现的数字表示四个互不相交的环。每个环中相邻位置恰好相距一个被禁止的马步。

\begin{array}{cccc}3&2&1&4\\1&4&3&2\\2&3&4&1\\4&1&2&3\end{array}

详细分析

把 $20\times20$ 棋盘划分为 $25$ 个互不相交的 $4\times4$ 方块，并在每个方块中按图示数组标号。任取一个固定标号，带有该标号的四个位置构成一个循环；循环中相邻位置的坐标差为 $(1,2)$ 或 $(2,1)$ ，所以距离为 $\sqrt{5}$ 。因此每个方块含有四个互不相交的马步循环。