取牙签智力游戏

gxqcn

这是个真实的故事。

去年国庆我们一家人到我老婆外公老家宜兴去玩，
聚了不少亲戚，不愧是教授之乡，里面有不少教授以及海外博士。
其中一位北京来的教授（我老婆喊他为舅舅），享受国务院津贴待遇的，
听说我儿子比较聪明，就给他出了一道题：
取了牙签三堆，要求与他轮流从任意堆里取走一根或数根牙签，也可以整堆取走，但不可不取，
谁最后一个取完则为胜，因为对方已无牙签可取。
当然，对于一个不到十岁的小孩，试着玩了几局只能获得几条简单规律。

今年国庆这位老人家路过苏州，特意到我家，
在饭桌上又和我儿子玩起了这个游戏，
让服务员拿来一盒牙签，分别取出3、5、7根组成三堆。
他比较能侃，说这个游戏曾考倒过很多人。

当时，没太在意。但事后仔细想想还确实蛮考脑筋的。
接近年尾了，大家可以在饭桌上同事间进行这个小游戏玩玩。

最近我无意间看到一篇关于此题的策略及推广，
过两天我将把它编辑过来。

Lwins_G

这是一个经典的博弈问题。（Nim）

详情可以查看：http://en.wikipedia.org/wiki/Nim

northwolves

先拿必胜

gxqcn

假设参与游戏的对手为A和B，A先拿，

1. 仅1堆：先拿者必胜，策略：全部拿完

2. 仅2堆：设为（k1,k2）

2.1 当k1=k2时，先拿者必败
　 策略：A在其中1堆中拿多少，B在另1堆中就拿多少，直到拿完为止。
2.2 当k1≠k2时，先拿者必胜
　　策略：A在数量多的1堆中拿走 abs（k1－k2）个，则变为局面2.1，B必败。

3. 仅3堆：设为（k1,k2,k3）

3.1 当k1=k2＝k3或其中任何2堆数量相等时，先拿者必胜
　 策略：A一次全部拿走牙签数量不同的1堆的所有牙签，则变为局面2.1，B必败。
3.2 当k1≠k2≠k3时，分析如下：

3.2.1 先用简单的例子，当（1，2，k）时

1) 当k＝3时，先拿者必败，分析如下：
　 A来取后只可能出现如下局面：
　 (1)（2，3） 如局面2.2 A必败
　 (2)（1，3） 如局面2.2 A必败
　 (3)（1，1，3） 如局面3.1 A必败
　 (4)（1，2） 如局面2.2 A必败
　 (5)（1，2，1） 如局面3.1 A必败
　 (6)（1，2，2） 如局面3.1 A必败
　 因此，当（1，2，3）时，先拿者必败
2) 当k≠3时，先拿者必胜
　 策略：A在第3堆中取走（k－3）枚牙签，则变为3.2.1的 1) 局面，A必胜
3) 同理，可分析（1，3，k）的局面
　 当k＝2时，先拿者必败
　 当k≠2时，先拿者必胜
4) 同理，还可分析（2，3，k）的局面
　 当k＝1时，先拿者必败
　 当k≠1时，先拿者必胜

3.2.2 认真分析 3.2.1 可得出结论

1) 当且仅当(k1)^(k2)^(k3)=0时（其中“^”为位异或运算符），先拿者必败
　也可表述为当(k1)^(k2)＝k3时，先拿者必败
2) (k1)^(k2)^(k3) ≠0时，先拿者必胜，策略：

(1) 分别计算(k1)^(k2)、(k1)^(k3)、(k3)^(k2)的值，设其分别为m3、m2、m1，
　 再分别比较k1与m1、k2与m2、k3与m3的大小，其中必有一个m值大，先从其对应k值的堆中取走（k－m）枚牙签。
(2) 重复第（1）步并利用1、2的结论即可。

举例说明：（3，4，7）
因3^4^7＝0，因此，先拿者必败
若A从第1堆取走1枚牙签，则变为（2，4，7）
此时，B如何应对呢？
2^4＝6，2^7＝5，4^7＝3，因此从第3堆中取走7-6＝1枚牙签，变为（2，4，6），因 2^4^6＝0，因此此局面仍然对A不利，
同理，下一步无论A怎样取，B可用同样的策略形成对A不利的局面，A必败。

4. 当n堆且各堆牙签数量相同时：设为（k,k,k，…k）时

4.1 当n为奇数时，先拿者必胜
　　策略：A先一次取走其中1堆中的所有牙签，B在其中另1堆中拿多少，A就在其对应数量（与B取牙签前数量）的另1堆中取多少，直到取完为止。
4.2 当n为偶数时，先拿者必败
　　策略：A在其中1堆中拿多少，B就在其对应数量（与A取牙签前数量）的另1堆中取多少，直到拿完为止。

5. 当n堆且各堆牙签数量均不相同时：设为（k1,k2,k3，…kn）且k1≠k2≠k3…≠kn时

5.1 当 (k1)^(k2)^…(kn) ≠0时，先拿者必胜
5.1 当(k1)^(k2)^…(kn)＝0时，先拿者必败
5.3 其策略可参照3.2.2

6. 当n堆且各堆牙签数量既有相同又有不相同时：设为（k1,k2,k3，…kn）时

1) 先将堆按数量分类，将数量相同的归为一类，
　假设k1数量的有p1堆，且p1>1
　K2数量的有p2堆，且p2>1
　…….
　Km数量的有pm堆，且pm>1
　其余 (q-m) 堆的数量均不同
　则p1+p2+…+pm＋ (q-m) ＝n
2) 再将p1到pm堆按奇偶分类。
3) 综合运用4、5的策略即可。

以上转自：http://wiki.kexue.com/index.php?doc-view-1622.html
但把里面的“硬币”换成了“牙签”，因为后者更容易大量获取。

hujunhua

我很早知道这个游戏的二进制策略，只是一直不明白，这种策略是如何解出来的。就是3.2.2，如何认真分析3.2.1，就能得到与异或有关的结论？

gxqcn

虽然整个思路是渐进的，但正如楼上所言，突然总结出与异或有关还是略显突兀，
哪位高手再来点解释？

hujunhua

我那时并不知道异或这个词，记住的策略是：
1、把每堆的数目换算成二进数，以竖式加法的形式按位对齐摞好；
2、把每列累加起来（得到每列1的数目），只要至少有一列累加数是奇数，就是必胜局面。策略就是：取走一堆上的若干牙签，改变这一堆所对应的行上的01串，使得各列的累加数都是偶数。
3、对手接着不论怎么取，由于他只能改变一行的01，01发生改变的列都会变成奇数，由于不能不取，至少有一列会发生改变。
4、然后，你按2的策略使得累加数再次恢复偶数，直到全部为0.

这样的解释已经让我懂得了策略的奥秘，但是，我那时不得不佩服想出这个策略的人。咋想出来的呢？

hujunhua

现在，游戏规则改为允许在其中1~2堆中取任意多（两堆合起来至少取1根）的牙签，策略又该如何总结呢？

gxqcn

少于3堆，先手胜；
否则，设法留给对方（1,1,1）的情形。

sheng_jianguo

对于郭站长提出的游戏的一般情况的对策，我以前研究过，比较难一点的是，最后拿的人是输（不是赢），在没看到任何有关资料情况下写了一篇数学论文，在本论坛发过一帖子“关于不增加组的乒乓球问题先手输赢的判定和取胜策略”，里面有我的论文，但不知为什么，好像没人感兴趣，下载数为0。