一局游戏在两个游戏人之间如下交替进行：游戏从一空堆开始。

当轮到一个游戏人时，他可以往堆中加进1，2，3或4枚硬币。

往堆中加进第100枚硬币的游戏人为得胜者。

确定在这局游戏中是游戏人A还是游戏人B能够确保取胜。

取胜的策略是什么？在学术论坛有博士家园，组合图论论坛确保取足5个硬币即可例题：两个人玩移火柴的游戏，桌子上有1000根火柴，每个人每次可以拿走1-7根火柴，拿走桌子上最后那根火柴的算输，问第一个人第一次要拿多少根火柴才能保证赢7根。

以后对方拿几根，你都要拿够凑足8根的数。

1000根和8根性质是一样的。

从抢30到NIM游戏的取胜策略（一）倒推法抢30是我国民间的一个两人游戏，具有很强的对抗性和娱乐性。

抢30游戏通常有两种玩法。

（1）两人从1开始轮流报数，每人每次可报一个数或两个连续的数，谁先报到30，谁就为胜方。

（2）两人从1开始轮流报数，每人每次可报一个数或两个连续的数，同时把两个人报出的所有数累加，谁先使这个累加数最先达到30，谁就为胜方。

解决最个问题的一般策略是用倒推法。

以（1）为例，要抢到30，必须抢到27；要抢到27，必须抢到24。

如此倒推回去，可得到一系列关键数30、27、24、21、18、……9、6、3。

根据以上分析，抢30游戏本身并不是一个公平的游戏，初始数和先后顺序已经决定了最后的结果，因为只有后报数者才能抢到3的倍数，后报数者有必胜策略。

（二）关键因子所有这些关键数都是3的倍数。

3是两个报数者年内能够报出的最大数与最小数的和。

在类似游戏中，我们把游戏者所能用到的最大数和最小数之和称之为关键因子k，关键数就是k的倍数.。

在抢30的游戏中，关键因子k等于3。

又例如，抢100报数游戏中，如果每人可报数为1至9个连续的自然数，谁先报到100谁就是胜利者。

这里的关键因子k就是可报最大数9和可报最小数1的和，即k=10。

报数获胜的策略就是：（1）让对方先报数；（2）每次报数为关键因子减去对方所报数。

这样自己每次所报数都是关键数。

如果对方一定要先报，你只能期待对方不懂策略或者大意出错了。

（三）不平衡因子在上述的抢30或者抢100的游戏中，最后数30是关键因子3的整数倍，最后数100是关键因子10的整数倍。

我们可以把这样的游戏称为平衡游戏，也就是最后报数与关键因子相除余数为0。

如果最后报数与关键因子相除有余数，这个游戏就可以称为不平衡游戏，其余数就是不平衡因子。

抢数不平衡游戏也是不公平的游戏，先报数者有必胜策略。

先报数者的获胜策略就是先消除不平衡因子，使其变成一个平衡游戏，先报数者随后就成为平衡游戏的后报数者。

例如，在抢30游戏中，两人从1开始轮流报数，每人每次可报1到3个连续的数，谁先报到30，谁就为胜方。

在这里，关键因子是4，不平衡因子是2。

又例如，抢100报数游戏中，如果每人可报数为1至10个连续的自然数，谁先报到100谁就是胜利者。

在这里，关键因子是11，不平衡因子是1。

在不平衡游戏中，如果先报数者不懂得游戏策略，懂得这个策略的后报数者需要不断计算不平衡因子，以便最后获胜。

（四）更多例子报数游戏里的最后数都是些比较小的数，因此用倒推法比较容易得到策略。

当我们把数变得大一些的时候，就变成了小学奥赛题。

如果掌握上述讨论中的关键因子和不平衡因子的计算，奥数题也变得迎刃而解了。

下面就是两个奥数例题。

（1）2008个空格子排成一排，第一格放有一个棋子。

两人做游戏，轮流移动这枚棋子。

每个人每次可前移1到5个格子，谁先把棋子移到最后一格，谁就是获胜者。

问怎样的策略才能保证获胜。

（2）桌上放着一堆火柴，共有5000根。

两个人轮流从中取火柴，每人每次取的火柴根数为1到8根，谁取了最后一根谁就输。

问怎样的策略才能保证获胜。

（五）进一步扩展到NIM游戏抢30的游戏是中国NIM游戏（也叫筹码游戏）的一种特例。

NIM游戏的一种经典表述为：有n堆火柴，每堆各有若干根。

两人轮流取出火柴，每次取出的根数不限但至少取1根，每次也只能从1堆里取火柴。

谁最后把火柴取完，谁就是获胜者。

问如何才能保证获胜。

获胜策略已由美国数学家C.L.Bouton分析完成，用到的是二进制和平衡状态概念。

其结论是：如果一开始火柴的总根数转化成二进制后各位数上的数字和都是偶数时，则是平衡状态，后取者必胜。

最简单的平衡态是（1，1），即2堆火柴，每堆各1根。

如果开始时火柴的状态处于不平衡状态，先取者必胜，其策略是取完后使火柴根数保持为平衡状态。

最简单的不平衡态是（1），即1根火柴。

例如，2堆火柴数都为2根，二进制记为（10，10），各位数之和为20，这是一个平衡态，则后取者必胜。

3堆火柴数分别为1根、2根、1根，二进制记为（1，10，1），各位数之和为12，这不是一个平衡态。

先取者先取掉中间一堆2根火柴，变成平衡状态（1，1），则先取者必胜。

下面的一道例题，可以用来练习NIM游戏的上述策略：有3堆火柴，根数分别为12、9、6.。

甲乙两人轮番从其中一堆中取出1根或几根火柴，取到最后一根者获胜。

先取者还是后取者有必胜策略，如何取胜？Nim游戏Nim游戏是博弈论中最经典的模型（之一？），它又有着十分简单的规则和无比优美的结论Nim游戏是组合游戏(Combinatorial Games)的一种，准确来说，属于“Impartial Combinatorial Games”（以下简称ICG）。

满足以下条件的游戏是ICG（可能不太严谨）：1、有两名选手；2、两名选手交替对游戏进行移动(move)，每次一步，选手可以在（一般而言）有限的合法移动集合中任选一种进行移动；3、对于游戏的任何一种可能的局面，合法的移动集合只取决于这个局面本身，不取决于轮到哪名选手操作、以前的任何操作、骰子的点数或者其它什么因素；4、如果轮到某名选手移动，且这个局面的合法的移动集合为空（也就是说此时无法进行移动），则这名选手负。

根据这个定义，很多日常的游戏并非ICG。

例如象棋就不满足条件3，因为红方只能移动红子，黑方只能移动黑子，合法的移动集合取决于轮到哪名选手操作。

通常的Nim游戏的定义是这样的：有若干堆石子，每堆石子的数量都是有限的，合法的移动是“选择一堆石子并拿走若干颗（不能不拿）”，如果轮到某个人时所有的石子堆都已经被拿空了，则判负（因为他此刻没有任何合法的移动）。

这游戏看上去有点复杂，先从简单情况开始研究吧。

如果轮到你的时候，只剩下一堆石子，那么此时的必胜策略肯定是把这堆石子全部拿完一颗也不给对手剩，然后对手就输了。

如果剩下两堆不相等的石子，必胜策略是通过取多的一堆的石子将两堆石子变得相等，以后如果对手在某一堆里拿若干颗，你就可以在另一堆中拿同样多的颗数，直至胜利。

如果你面对的是两堆相等的石子，那么此时你是没有任何必胜策略的，反而对手可以遵循上面的策略保证必胜。

如果是三堆石子……好像已经很难分析了，看来我们必须要借助一些其它好用的（最好是程式化的）分析方法了，或者说，我们最好能够设计出一种在有必胜策略时就能找到必胜策略的算法。

定义P-position和N-position，其中P代表Previous，N代表Next。

直观的说，上一次move的人有必胜策略的局面是P-position，也就是“后手可保证必胜”或者“先手必败”，现在轮到move的人有必胜策略的局面是N-position，也就是“先手可保证必胜”。

更严谨的定义是：1.无法进行任何移动的局面（也就是terminal position）是P-position；2.可以移动到P-position的局面是N-position；3.所有移动都导致N-position的局面是P-position。

按照这个定义，如果局面不可能重现，或者说positions的集合可以进行拓扑排序，那么每个position或者是P-position或者是N-position，而且可以通过定义计算出来。

以Nim游戏为例来进行一下计算。

比如说我刚才说当只有两堆石子且两堆石子数量相等时后手有必胜策略，也就是这是一个P-position，下面我们依靠定义证明一下(3,3)是一个P是一个P是一个P-position。

首先(3,3)的子局面（也就是通过合法移动可以导致的局面）有(0,3)(1,3)(2,3)（显然交换石子堆的位置不影响其性质，所以把(x,y)和(y,x)看成同一种局面），只需要计算出这三种局面的性质就可以了。

(0,3)的子局面有(0,0)、(0,1)、(0,2)，其中(0,0)显然是P-position，所以(0,3)是N-position （只要找到一个是P-position的子局面就能说明是N-position）。

(1,3)的后继中(1,1)是P-position（因为(1,1)的唯一子局面(0,1)是N-position），所以(1,3)也是N-position。

同样可以证明(2,3)是N-position。

所以(3,3)的所有子局面都是N-position，它就是P-position。

通过一点简单的数学归纳，可以严格的证明“有两堆石子时的局面是P-position当且仅当这两堆石子的数目相等”。

根据上面这个过程，可以得到一个递归的算法——对于当前的局面，递归计算它的所有子局面的性质，如果存在某个子局面是P-position，那么向这个子局面的移动就是必胜策略。

当然，可能你已经敏锐地看出有大量的重叠子问题，所以可以用DP 或者记忆化搜索的方法以提高效率。

但问题是，利用这个算法，对于某个Nim游戏的局面(a1,a2,...,an)来说，要想判断它的性质以及找出必胜策略，需要计算O(a1*a2*...*an)个局面的性质，不管怎样记忆化都无法降低这个时间复杂度。

所以我们需要更高效的判断Nim游戏的局面的性质的方法。

直接说结论好了。

(Bouton's Theorem)对于一个Nim游戏的局面(a1,a2,...,an)，它是P-position当且仅当a1^a2^...^an=0，其中^表示异或(xor)运算。

怎么样，是不是很神奇？我看到它的时候也觉得很神奇，完全没有道理的和异或运算扯上了关系。

但这个定理的证明却也不复杂，基本上就是按照两种position的证明来的。

根据定义，证明一种判断position的性质的方法的正确性，只需证明三个命题：1、这个判断将所有terminal position判为P-position；2、根据这个判断被判为N-position的局面一定可以移动到某个P-position；3、根据这个判断被判为P-position 的局面无法移动到某个P-position。

第一个命题显然，terminal position只有一个，就是全0，异或仍然是0。

第二个命题，对于某个局面(a1,a2,...,an)，若a1^a2^...^an!=0，一定存在某个合法的移动，将ai改变成ai'后满足a1^a2^...^ai'^...^an=0。