1.12 NIM（2）“拈”游戏分析

题意：给N块石头，玩家X把石头分成若干堆，然后按照XYXY...这样的顺序取石头，每次可以取一堆石头中的任意数目（大于0）个石头，谁先取完谁胜。

此题目的关键在于证明一个规律，即N为偶数的时候，先动手的输，N为奇数时，先动手的人赢。

假设N个石头被分成m堆，为（A1，A₂，……，Am），最后取光了必定为（0，0，……，0），将此时（A1，A₂，……，Am）全部异或操作，结果为0。

三条结论：

1）N为奇数的时候，XOR（A1，A₂，……，Am）的结果为奇数，这个很明显。

2）当XOR（A1，A₂，……，Am）不等于0的时候，总有一种取石子的方法可以把XOR（A1，A₂，……，Am）变成0，这个证明也简单。

3）当XOR（A1，A₂，……，Am）等于0的话，任何改变都会让其不等于0，这个证明也不难。

由上面三条结论可以知道，只要X每次都给对方留一个XOR（A1，A₂，……，Am）等于0的状态，则X必胜，因为此状态最后一定会到达石头取光的时候的0的状态。

在游戏的回合过程中，以独占获胜所需要的状态来实现最终的胜利，这是一种巧妙的数学建模方法，隐藏的了问题的纷繁复杂，直击要害。

PS：回过头看1.11，实际上和这道题目的道理是一样的。

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

题意：两堆石头，一次可以从一堆里面取任意个，也可以从两堆里面取数量相等的石头，A和B两个人轮流取，谁先取完谁胜。

解法一是一种打表筛选的方法，通过初始不安全局面来排除所有安全局面，找到新的不安全局面，迭代查找，虽然有点暴力，但是的确是有效的。

解法二是利用直接计算不安全局面的通项公式，解法比较“数学”，书中附录中有证明。

此题也是让先手保持在安全状态，和之前的几个NIM独占某种状态是一样的，却别在于，前两个NIM的安全状态很明显，或者很容易得到，而这个就需要自己用某种方法去寻找了。