作者：matrix67
原文地址：http://www.matrix67.com/blog/archives/6784#more-6784
让我们来玩一个游戏。把某个国际象棋棋子放在棋盘上，两人遵循棋子的走法，轮流移动棋子，但只能将棋子往左方、下方或者左下方移动。谁先将棋子移动到棋盘的最左下角，谁就获胜。如果把棋子放在如图所示的位置，那么你愿意先走还是后走？显然，答案与我们放的是什么棋子有关。
![]()
这个游戏对于兵来说是没有意义的。在如图所示的地方放马或者放象，不管怎样都无法把它移动到棋盘的最左下角，所以我们也就不分析了。因此，我们只需要研究王、后、车三种情况。
在国际象棋中，车每次可以横着或竖着走任意多格。在上述游戏中，受到规则的限制，车每次只能向左或者向下走任意多格。如果问题中的棋子是车，答案就非常简单了：你应该选择先走。你应该直接把车移到棋盘对角线上的位置（如左图所示），然后不管对方怎么走，你都把它移回到棋盘的对角线上。这样，你就能保证必胜了。
![]()
在国际象棋中，王每次可以横着、竖着或者斜着走一格。在上述游戏中，受到规则的限制，王每次只能向左、向下或者向左下方走一格。如果问题中的棋子是王，分析出问题的答案也不算太难：你应该选择先走。你应该直接把王移到棋盘的“奇格”里（如右图所示），然后不管对方怎么走，你都可以把它再次移到某个“奇格”里。这样，你就能保证必胜了。
在国际象棋中，皇后每次可以横着、竖着或者斜着走任意多格。在上述游戏中，受到规则的限制，皇后每次只能向左、向下或者向左下方走任意多格。如果问题中的棋子是皇后，那么你应该选择先走还是后走呢？这次，问题就没那么简单了。
这个“挪动皇后”的游戏是由 Rufus Isaacs 在 1960 年左右提出来的。给定皇后在棋盘上的初始位置，如何判断出谁有必胜策略呢？ Isaacs 给出了一个分析方法。
![]()
首先，第一行上的所有位置，第一列上的所有位置，以及对角线上的所有位置，都能一步直接走到棋盘的最左下角。我们可以从最左下角的位置出发，画出三条射线，把这些位置全都划掉。如果皇后位于被划掉的位置上，那么先走的人就会获胜。此时，棋盘上出现了两个死角。如果皇后在这两个地方，先走的人不得不把皇后挪到刚才被划掉的位置上，因而后走的人就必胜了。因而，从这两个地方出发，画出三条射线，被划掉的位置又是先走的人就会获胜的位置，先走的人只需要把皇后挪到这两个地方即可。此时，棋盘上又会出现两个新的死角，它们又是后走的人必胜的位置……不断这样递推下去，我们就能分析出，皇后在哪些地方时先走的人必胜，皇后在哪些地方时后走的人必胜。之前我们曾问，当皇后位于标有 × 的格子时你应该选择先走还是后走，现在我们就知道答案了：你应该后走才对。
那么，在“挪动皇后”的游戏中，哪些位置是后走的人必胜的位置呢？
![]()
画出更大的棋盘，将刚才的操作再多重复几次后，我们看见了一个非常明显的规律：这些位置大致形成了两条直线。再仔细观察，你会发现，每行每列里恰好有一个这样的位置。有没有什么公式不用递推就能找出这些位置呢？它们为什么会形成这么两条直线呢？为什么每行每列里有且仅有一个这样的位置呢？看来，这里面还有很深的水。
令 Isaacs 万万没有想到的是，这个游戏虽然是他发明的，但由此引申的问题却已经被前人解决了。 1907 年，荷兰数学家 Willem Abraham Wythoff 提出了一个双人对弈游戏，后来人们把它叫作 Wythoff 游戏。游戏规则是这样的。地上有两堆石子，其中一堆有 m 个石子，另外一堆有 n 个石子。两名玩家轮流取走石子，规定每次要么从其中一堆石子中取走任意多个石子，要么从两堆石子中取走相同数量的石子。等到谁没有石子可取了，谁就输了。也就是说，取到最后一个石子的玩家获胜。 Martin Gardner 认为， Wythoff 本人甚至也不是这个游戏最早的发明者——其实中国很早就有了这个游戏，人们把它叫作“捡石子”。
容易看出， Wythoff 游戏和“挪动皇后”是完全等价的。把棋盘从下到上各行依次标为 0, 1, 2, 3, …，把棋盘从左到右各列依次标为 0, 1, 2, 3, …，那么皇后移动时坐标变化的规则，正好与 Wythoff 游戏中两堆石子数量变化的规则是相同的。而两个游戏的目标也是相同的：谁先将游戏状态变为 (0, 0) ，谁就获得胜利。因此，这两个游戏完全等价。
由于状态 (m, n) 和 (n, m) 本质相同，因而我们可以把游戏状态看作是无序数对，并约定在书写时总把较小的数写在前面。也就是说，今后 (1, 2) 和 (2, 1) 就统一用 (1, 2) 来表示了。另外，只要数对里面至少有一个数不为 0 ，我们就说这是一个非零数对。我们的问题就是，哪些非零数对所对应的游戏状态是后行者必胜的。
Wythoff 给出的答案异常简单——所有这样的数对从小到大依次为：
([1 · φ], [1 · φ2]), ([2 · φ], [2 · φ2]), ([3 · φ], [3 · φ2]), ([4 · φ], [4 · φ2]), …
其中 φ = (√5 + 1) / 2 ， [x] 表示不超过 x 的最大整数（当 x ≥ 0 时， [x] 可以简单地理解为取 x 的整数部分）。不妨把上述序列叫作序列 W 。稍作计算可知，序列 W 的前几项为：
(1, 2), (3, 5), (4, 7), (6, 10), (8, 13), …
对照前面那个棋盘图，我们可以看到，序列 W 还真挺靠谱。 Wythoff 证明了，序列 W 确实就是正确的答案，这是因为序列 W 满足以下三个条件：
条件 1 ： W 当中的任何一个数对都无法一步变成 (0, 0)
条件 2 ： W 当中的任何一个数对都无法一步变成 W 当中的另一个数对
条件 3 ： W 之外的任何一个非零数对都可以一步变成 (0, 0) 或 W 当中的某一个数对
这样的话，当游戏状态为 W 当中的数对时，先走的人只能把游戏状态变为 W 之外的非零数对，后走的人即使赢不了，也总能把游戏状态移回到 W 当中。不断这样循环下去，后走的人就赢定了。所以，如果序列 W 真的满足上面三个条件，刚才的公式就是正确的了。那么，序列 W 为什么满足上面三个条件呢？ Wythoff 进一步指出，这是因为序列 W 满足以下三个性质：
性质 1 ： W 里面正好既无重复又无遗漏地包含了每一个正整数
性质 2 ： W 当中各项里的两数之差依次为 1, 2, 3, …
性质 3 ： W 当中各项里的较小数依次递增
我们先来说明这三个性质为什么能推出前面的三个条件，然后再来说明这三个性质本身为什么都是成立的。性质 1 和性质 2 告诉我们： W 当中用到的数都大于 0 ，且没有重复的情况；各个数对里的两数之差也都大于 0 ，而且也没有重复的情况。这能立即推出前面的条件 1 和条件 2 。现在，假设 (a, b) 是 W 之外的某个非零数对。如果 a = 0 或者 a = b ，那么 (a, b) 可以直接变成 (0, 0) 。接下来，我们假设 0
接下来，我们来证明序列 W 满足这三个性质。性质 1 可以直接由 Beatty-Rayleigh 定理推出。 Beatty-Rayleigh 定理说的是，若正无理数 α 和 β 满足 1 / α + 1 / β = 1 ，则数列 [1 · α], [2 · α], [3 · α], … 和 [1 · β], [2 · β], [3 · β], … 既无重复又无遗漏地包含了所有的正整数。由于 φ 和 φ2 就满足 1 / φ + 1 / φ2 = 1 ，所以序列 W 里的所有数既无重复又无遗漏地包含了所有的正整数。
为了保持文章的完整性，我们给出 Beatty-Rayleigh 定理的证明。 Beatty-Rayleigh 定理有很多证明方法，下面这种方法是我最喜欢的一种。首先注意到，如果 x 和 y 都不是整数，那么 [x] 严格地小于 x ，[y] 严格地小于 y ，从而 [x] + [y]
回到原问题。显然，在数列 [1 · α], [2 · α], [3 · α], … 中，小于 n 的正整数有 [n / α] 个。显然，在数列 [1 · β], [2 · β], [3 · β], … 中，小于 n 的正整数有 [n / β] 个。因此，在这两个数列中，小于 n 的正整数共有 [n / α] + [n / β] 个。由于 α 和 β 都是无理数，因此 n / α 和 n / β 不可能为整数，由刚才的结论， [n / α] + [n / β] 一定介于 n / α + n / β – 2 和 n / α + n / β 之间，即 n – 2 和 n 之间。但是， [n / α] + [n / β] 是个整数，因而它精确地等于 n – 1 。
这说明，前 n – 1 个正整数在两个数列中一共出现了 n – 1 次，这对于所有 n 都成立。于是，正整数 1 必须且只能出现在其中一个数列中，正整数 2 必须且只能出现在其中一个数列中，以此类推，每一个新的正整数都必须且只能出现在其中一个数列中。
序列 W 的性质 2 则是， W 当中各项里的两数之差依次为 1, 2, 3, … ，也就是说第 n 个数对里的两数之差恰好为 n 。这一点也是很容易看出来的。由于 φ 满足 1 + φ = φ2 ，因而 n + n · φ = n · φ2 ，即 n · φ 和 n · φ2 正好相差 n 。如果两个数正好相差 n ，那么这两个数的整数部分显然也就正好相差 n 。这就证明了序列 W 满足性质 2 。
序列 W 的性质 3 则是， W 当中各项里的较小数依次递增，即 [1 · φ], [2 · φ], [3 · φ], … 依次递增。这就更显然了：在数列 1 · φ, 2 · φ, 3 · φ, … 中，后一项总比前一项大 φ ≈ 1.618 > 1 ，因此即使取整后，后一项也一定严格地大于前一项。注意到，性质 2 和性质 3 结合起来可以告诉我们， W 当中各项里的较大数也是依次递增的。
至此，我们就完整地证明了， Wythoff 提出的公式确实准确地给出了 Wythoff 游戏（也就是“挪动皇后”游戏）中后行者必胜的状态。这也顺便把我们之前挖的坑填上了。为什么把后行者必胜的状态标在棋盘上，会形成两条直线呢？看看序列 W 的公式，你就知道了：这是因为，每个数对里的前后两项之比（即横纵坐标之比）都是固定的。为什么棋盘的每行每列里都有且仅有一个标记呢？这其实完全是由序列 W 的性质 1 带来的结果。
未完，请移步下篇！
