1.13　NIM（3）两堆石头的游戏

在前面两个题目中，我们讨论了被称为“NIM（拈）”的这种游戏及其变种的玩法和必胜策略，下面我们将讨论这类游戏的另一种有趣的玩法：

假设有两堆石头，有两个玩家会根据如下的规则轮流取石头：

每人每次可以从两堆石头中各取出数量相等的石头，或者仅从一堆石头中取出任意数量的石头。

最后把剩下的石头一次拿光的人获胜。

例如，对于数量分别为1和2的两堆石头，取石头的第一个玩家必定将会输掉游戏。因为他要么只能从任意一堆中取一块石头，要么只能从两堆中各取出一块石头。但无论他采用哪种方式取，最后，剩下的石头总是恰好能被第二个玩家一次取光。

若定义一个函数如下：

分别是两堆石头的数量

要求返回一个布尔值，表明首先取石头的玩家是否能赢得这个游戏。

分析与解法

拿到这个题目，你也许会想，有两个玩家，有两种取石头的方法，每个人还必须按照比较理性的方法取石头……头绪的确比较多。如果你觉得这个题目比较难的话，不妨从简单的问题入手，还记得以前学过的构造质数的“筛子”方法么？

怎样才能找出从2开始的质数呢？我们先把所有数字都排列出来：

既然2是质数，那么2的倍数就不是质数，那我们就把它们都“筛掉”：

那么下一数字3，它没有被筛掉，意味着它不能被小于它的数整除，所以它就是一个质数！于是我们再把3的倍数筛掉，得到下表：

如法炮制，我们得到了后面的质数：5，7，…

【解法一】

回到这个NIM的问题，我们能否也“筛”一回？表1-1显示了在（10，10）范围内两堆石头的可能组合，由于它具有对称性，所以我们不用处理另一半的表格，另外，像（0，0）、（1，0）这样的特殊情况已经处理了。所以我们先把它们筛掉。

表1-1　（10，10）范围内石头可能的组合

首先我们定义：先取者有必胜策略的局面为“安全局面”，而先取者无必胜策略的局面为“不安全局面”。

我们把（1，1），（2，2），…，（10，10）的安全局面筛掉。如表1-2所示：

表1-2　筛去安全局面的组合

那么这个表里最前面的一个组合就是（1，2），通过简单的分析，我们知道这是一个必输的局面——“不安全局面”，那么根据规则可以一步到达（1，2）这个局面的数字组合如（1，3），（1，4），（1，n）等，都是安全局面——我们可以把这些组合全部筛掉，（1，n）都可以经过一步转换变成（1，2），（2，n）也是可以一步转换成（2，1）的（它等价于（1，2）），所以也要被筛掉。（n＋1，n＋2）也是如此，同样可以被筛掉。这样我们的表就简洁多了（如表1-3所示）。

表1-3　筛去安全局面的组合

现在表上的下一组数是什么呢？对，是（3，5）。和（1，2）一样，这个没有被筛掉的组合就是我们的下一个不安全局面。显然，（3，5）组合的任意一个符合规则的变化都是一个“安全局面”。

好了，得到了（3，5），我们就要把（3，n），（n，3），（5，n），（n，5），（3＋n，5＋n）都筛掉。于是我们得到了表1-4：

表1-4　安全局面的结果

这时，（4，7）成为另一个不安全局面，经过筛选之后，（6，10）又是一个……

看到规律了吧。一般而言，第n组的不安全局面（a_n，b_n）可以由以下定义得到：

1．a₁＝1，b₁＝2。

2．若a₁，b₁，…，a_n－1，b_n－1已经求得，则定义a_n为未出现在这2n－2个数中的最小整数。

3．b_n＝a_n＋n。

做成表就是（如表1-5所示）：

表1-5　安全局面表

因此，我们可以根据上述定义，从第一个不安全局面（1，2）出发，依次向上推理，直到推理出足够的不安全局面来判定一个随机给定的状态下，先取者是否能够获胜。具体做法就是设两堆石头中较小那堆的数量为x，从（1，2）开始向上推理，直到a_n大于等于x为止，此时我们就得到了a_n小于等于x的所有不安全局面。如果x恰好等于某一不安全局面的a_n值，只要根据另一堆石头的数量是否恰好与x对应的b_n相等，就可以判断出先取者是否有办法赢得游戏。如果x不等于任意一个不安全局面的a_n值，则先取者必胜。

根据上述分析，可以写出如下代码：

代码清单1-18　C#自底向上的解法

解法看上去虽然直观，但是效率并不高，因为它是一种自底向上推理的算法，算法的复杂度为O（N）。

【解法二】

我们看看能否找出不安全局面的规律，最好有一个通用的公式可以表示。所有不安全局面（{＜1，2＞，＜3，5＞，＜4，7＞，＜6，10＞，…}）的两个数合起来就是所有正整数的集合，且没有重复的元素，而且所有不安全局面的两个数之差的绝对值合起来是所有正整数的集合，且没有重复的元素，如：2－1＝1，5－3＝2，7－4＝3，10－6＝4，…

看来不安全局面是有规律的。的确，我们可以证明有一个通项公式能计算出所有不安全局面，即：

具体证明见文后附1。

有了通项公式，我们就能更加简明地实现函数bool nim(n，m)，这个函数的时间复杂度为O（1）。

代码清单1-19

解法二将算法的复杂度降低到了O（1），由此可见，掌握良好的数学思维能力，往往能在解决问题时起到事半功倍的效果。“拈”游戏还有许多有趣的变形和扩展，感兴趣的读者不妨思考一些新的游戏规则，并尝试寻找一下对应的必胜策略。

扩展问题

1．现在我们已经给出了一个判断先取者是否能够最终赢得游戏的判断函数，但是，游戏的乐趣在于过程，大家能不能根据本题的思路给出一个赢得游戏的必胜策略呢？即根据当前石头个数，给出当前玩家下一步要怎么取石头才能必胜。

2．取石头的游戏已经不少了，但是我们还有一种游戏要请大家思考，我们姑且叫它NIM（4）：

两个玩家，只有一堆石头，两人依次拿石头，最后拿光者为赢家。取石头的规则是：

（a）第一个玩家不能拿光所有的石头。

（b）第一次拿石头之后，每人每次最多只能拿掉对方前一次所拿石头的两倍。

那么，这个游戏有没有必胜的算法？（提示：好像和Fibonacci数列有关。）

【附1】解法二的证明

准备

我们将两堆石头的数目记作＜a，b＞。对任意正整数a，如果＜a，b₁＞和＜a，b₂＞都是不安全局面，则b₁＝b₂（假设b₁＞b₂，则先取者可以通过在＜a，b₁＞中拿b₁－b₂个石头来让对手达到＜a，b₂＞的不安全局面，这与没有必胜策略矛盾，所以说a和b是一一对应的）。

定义

■　L＝{＜a_n，b_n＞|＜a_n，b_n＞是不安全局面}＝{＜1，2＞，＜3，5＞，＜4，7＞，＜6，10＞，…}

■　A_n＝{a₁，a₂，…，a_n}，B_n＝{b₁，b₂，b_n}

■　A＝{a₁，a₂，…，a_n，…}

■　B＝{b₁，b₂，…，b_n，…}

■　n为除0以外的自然数集

因为对称性和a_n＝b_n时为安全局面，我们可以定义a_n＜b_n，同时还可以定义a_n＜a_n＋1（n＝1，2，3，…）。由“准备”中的结论我们知道A∩B＝φ（否则存在x∈A∩B，使得＜a，x＞，＜x，b＞（其中a∈A，b∈B，a＜x＜b）都是不安全局面，这与“准备”中的结论矛盾）。后面我们还将看到A∪B＝N（N是0除外的自然数集）。

证明

从解法一中我们得知，所有的不安全局面＜a_n，b_n＞都满足：a_n＋n＝b_n，且a_n＝min（N－A_n－1∪B_n－1），接下来我们将采用数学归纳法来证明这个结论：

1．显然n＝1时，结论成立；

n＝1时，根据定义得a₁＝1，b₁＝2，记作＜1，2＞。按照游戏规则，先取者要么取光其中一堆石头，要么从第二堆中取出一块石头，要么从两堆中各取一块石头。无论先取者怎么取，后取者都将取得最后的石头而获胜。

2．假设n＜k（k＞1）时结论成立，我们现在来证明n＝k时结论也成立，即a_k＋k＝b_k，其中a_k＝min（N－A_k－1∪B_k－1）。为了证明方便，记a=a_k。

（a）显然<a，x>（x＜＝a）都是安全局面（根据a定义和归纳假设）。

（b）<a，a＋x>（x＝1，2，…，k－1）是安全局面，因为总可以分别从两堆石头中拿走a－a_x，以到达不安全局面<a_x，a_x＋x>。

（c）<a，a＋k>是不安全局面，可以通过枚举所有取石头的可能情况来证明，如下所示：

i．从a中取走a－x块石头（x＝1，2，…，a－1，a），剩下<x，a＋k>是安全局面。因为即使存在不安全局面<x，x＋t>，因为有x＜a，t＜k，所以x＋t＜a＋k。

ii．从a＋k中取，只能到达不安全局面。前面（a）和（b）已经证明了<a，x>（x＜＝a）和<a，a＋x>（x＝1，2，…，k－1）都是安全局面。

iii．分别从两堆中取x块石头（x＝1，2，…，a），剩下的<a_k－x，a_k＋k－x>一定是安全局面。因为假设存在<a_k－x，a_k－x＋t>的不安全局面，由于有t＜k，所以a_k－x＋t＜a_k＋k－x，假设不成立。

（d）<a，a＋x>（x＞k）是安全局面：

i．由（c）可知，在第二堆中取x－k即可达到不安全局面<a，a＋k>。

所以，当n＝k时，有b_k＝a_k＋k，其中a_k＝min（N－A_k－1∪B_k－1），结论成立。由数学归纳法知，对任意正整数n原结论成立。

推论：A∪B＝N（读者可以用反证法证明），又因为我们已经得到A∩B＝φ，所以A\B是N的一个分划。这个推论会在下面的求解中应用到。

求解不安全局面

我们已经得到不安全局面的一些性质，现在来求解不安全局面。

定理：如果正无理数a，b满足1/a＋1/b＝1，则{[an]|n∈N}/{[bn]|n∈N}是N的一个分划，其中[]为高斯记号，[an]表示对an向下取整。

现在我们就根据上述定理来构造一个满足不安全局面的分划：

取无理数a，b，其满足1/a＋a/b＝1；

令x_n＝[an]，y_n＝[bn]，y_n＝x_n＋n（n＝1，2，3，4，…）；

则{x_n|n∈N}/{y_n|n∈N}是N的一个分划。我们在加上一个限制条件：令y_n＝x_n＋n，即[bn]＝[an]＋n＝[（a＋1）*n]，因为这个等式对所有的n∈N成立，所以必有b＝a＋1（否则总能找到足够大的n使得等式不成立）。

求解二元一次方程组：

可得：

下面我们将看到这个x_n ，y_n就是我们要求的a_n ，b_n：

1．显然x₁＝a₁，且满足相同的递推关系，所以我们只需证明x_n＝min（N－X_n－1∪Y_n－1），

2．其中X_n＝{x₁，x₂，…，x_n}，Y_n＝{y₁，y₂，…，y_n}，这是显然的，否则，由于x_n、y_n具有严格的单调性，且y_n＞x_n，那么N－X∪Y将会不为空，与X/Y是N的划分矛盾。

所以x_n，y_n就是我们所要求的a_n，b_n。

即a_n＝[an]，b_n＝[bn]，其中：

至此，对于任意给定的一个状态<x，y>，我们都可以通过判断x是否等于某个[an]，且y是否等于对应的[bn]，来判断<x，y>是否为一个不安全局面。或者我们也可以通过判断y－x（假设x＜＝y）是否等于[a]*（y－x）来判断<x，y>是否为一个不安全局面。同理，若<x，y>是一个安全局面，我们也可以通过这个判定法来取合适数量的石头，从而令对手达到某一个不安全局面。

【附2】Python的程序解法

前面提到的解法一的代码是由C#写成的，MSRA里有位工程师给出了一个Python的解法，思路与之类似，大家不妨分析一下哪种解法效率更高？下面是自底向上解法的Python源代码：

代码清单1-20

很快，这位工程师又想出了另一种解法，不过这次他不是从n＝1的不安全局面自底向上推理的，而是反其道行之，自顶向下查找，代码如下，读者不妨研究一下：

代码清单1-21