捡石子游戏、 Wythoff 数表和一切的 Fibonacci 数列

正文

请到「今天看啥」查看全文

这个“挪动皇后”的游戏是由 Rufus Isaacs 在 1960 年左右提出来的。给定皇后在棋盘上的初始位置，如何判断出谁有必胜策略呢？ Isaacs 给出了一个分析方法。

首先，第一行上的所有位置，第一列上的所有位置，以及对角线上的所有位置，都能一步直接走到棋盘的最左下角。我们可以从最左下角的位置出发，画出三条射线，把这些位置全都划掉。如果皇后位于被划掉的位置上，那么先走的人就会获胜。此时，棋盘上出现了两个死角。如果皇后在这两个地方，先走的人不得不把皇后挪到刚才被划掉的位置上，因而后走的人就必胜了。因而，从这两个地方出发，画出三条射线，被划掉的位置又是先走的人就会获胜的位置，先走的人只需要把皇后挪到这两个地方即可。此时，棋盘上又会出现两个新的死角，它们又是后走的人必胜的位置……不断这样递推下去，我们就能分析出，皇后在哪些地方时先走的人必胜，皇后在哪些地方时后走的人必胜。之前我们曾问，当皇后位于标有 × 的格子时你应该选择先走还是后走，现在我们就知道答案了：你应该后走才对。

那么，在“挪动皇后”的游戏中，哪些位置是后走的人必胜的位置呢？

画出更大的棋盘，将刚才的操作再多重复几次后，我们看见了一个非常明显的规律：这些位置大致形成了两条直线。再仔细观察，你会发现，每行每列里恰好有一个这样的位置。有没有什么公式不用递推就能找出这些位置呢？它们为什么会形成这么两条直线呢？为什么每行每列里有且仅有一个这样的位置呢？看来，这里面还有很深的水。

令 Isaacs 万万没有想到的是，这个游戏虽然是他发明的，但由此引申的问题却已经被前人解决了。 1907 年，荷兰数学家 Willem Abraham Wythoff 提出了一个双人对弈游戏，后来人们把它叫作 Wythoff 游戏。游戏规则是这样的。地上有两堆石子，其中一堆有 m 个石子，另外一堆有 n 个石子。两名玩家轮流取走石子，规定每次要么从其中一堆石子中取走任意多个石子，要么从两堆石子中取走相同数量的石子。等到谁没有石子可取了，谁就输了。也就是说，取到最后一个石子的玩家获胜。 Martin Gardner 认为， Wythoff 本人甚至也不是这个游戏最早的发明者——其实中国很早就有了这个游戏，人们把它叫作“捡石子”。

请到「今天看啥」查看全文