NIm游戏-取数之超一流难题

NIm游戏
三堆火柴分别有2001根、2002根、2003根。甲、乙两人轮流从中取火柴。规则是：每人每次只能从其中的一堆取，最少要取一根，最多可以全部取走，可以任意选择，谁取完最后一堆的最后一根就获胜。如果甲先取，要保证获胜，他应该制定怎样的策略。

小豆120

甲先把2001取剩下1个.  乙把另两堆之一取剩下A个, 如A是偶数,甲将第3堆取剩下A+1:
                                                                          如A是奇数,甲将第3堆取剩下A- 1:
                最后留给乙1,2,3 甲必赢.
如果乙操作失误,使其中两堆相等或只剩下两堆,甲会赢的更轻松!

cutmiss

小豆给出了一个策略，我下面补充一些更详细些的内容。没有证明，证明是容易的，如果哪位有兴趣，希望能自己试试。我觉得重要的是想法~~~~~


我小小时候，玩过这个游戏，是3，5，7根火柴。当时也不知道其原理，也根本不知道啥叫2进制，只是就数论数，找出过取胜策略。现在回头看看，觉得当时的想法很幼稚。

这个游戏，国外叫nim，我们一般翻译为“尼姆”，也有翻译为“拈”，似乎后者更为贴切；据说是从中国流传出去的（这叫我想起围棋和四大发明了~~~）。

原始的提法是：n堆棋子，每堆分别为m(1), m(2), ..., m(n)个棋子，甲乙轮流取子，轮到者不能不取，每次只能在一堆中取，且可取某堆中任意多子；取最后子者胜；问先手有必胜策略的条件是什么？在该条件满足时如何获胜？

后来还有很多的变种，例如限制取子个数、改为取最后子者负等等，似乎很多。

1堆2堆的情形是平凡的，这题目给出的是一个3堆的情形。

这个古老的游戏的理论上的解决，是哈佛的Chales Leonard Bouton用不进位的2进制数加法来给出的一个详尽的解法。大意如下：

我们把每堆火柴数用2进制描述

2001=11111010001
2002=11111010010
2003=11111010011
不进位相加，和为33333030022

这里需要两个概念，安全(safe)状态：不论对方如何拿，我都有必胜策略；不安全(unsafe)状态：不是安全状态。

我们需要的是，在我拿每次过之后的状态是安全状态。
那么，怎么判断是安全状态还是不安全状态？安全状态下拿子后，就一定不是安全状态吗？从不安全状态拿子后，一定可以变成安全状态吗？

一个简单的原则是：如果我们按上述方式得到的2进制不进位的加法和各个数字都是偶数，那么就是一安全状态，若有奇数，就是不安全状态。

如果一开始的状态是安全的，那么，无论如何拿，先手总是将不安全状态留给后手；如果一开始的状态是不安全的，那么，先手总是有策略将安全状态留给后手。因为最后的状态（无子可拿）是安全的，所以第一种情况下，后手有必胜策略；而第二种情况下，先手有必胜策略。

就本题而论，开始的状态是不安全的（有奇数3），所以，先手有必胜策略。
最直观的想法是从某堆中取走11111010000（2进制）个，即10进制中的2000个。
这样那个和就变成22222020022，从而获得安全状态。
那么，无论后手如何拿，总是获得不安全状态，而先手总是能把不安全状态变成安全状态（为什么呢？）

eagle119

敦敦教导,佩服之至!
用2进制是最聪明的办法

一个简单的原则是：如果我们按上述方式得到的2进制不进位的加法和各个数字都是偶数，那么就是一安全状态，若有奇数，就是不安全状态。

可以这么考虑上述原则：
我们将“2进制不进位的加法和各个数字都是偶数”的状态记为状态S；将“2进制不进位的加法和各个数字包含奇数”的状态记为状态T；那么每一状态都必定是这两种不同的状态之一。
我们可以证明下面的事实：

1、有确定的策略将状态T变为状态S（可从棋子最多的堆中拿子，规则是：设2进制的各位和的第i位为i(j)，按位定义一个新的2进制数n，若i(j)为奇数，则n的第i位为1，若i(j)为偶数，则n的第i位为0，n计算出来后，就从最多那堆拿掉n个子）；

2、S状态下，无论如何操作，总是将状态S变为状态T（因为他必须拿棋子，而且只能在一堆里拿棋子）；

3、无子状态是状态S；

4、综合1、2，我们可得到：如果我们面对状态T，总可按1的策略，将状态变成状态S，而使对方面对状态S，那么对方势必将状态S变成状态T。那么，只要面对状态T，总能操作后使对方面对状态S。每次操作后棋子总数是减少的，终将使对方面对无子状态。而对方却不能使我们面对S状态。

所以，面对状态T时，是有必胜策略的，但这时我们是不安全的，还需要我们操作，操作正确，我们就是安全的，所以把操作后的状态S称为安全状态――我们从不安全状态，通过正确的操作（即策略），进入了安全状态。

天外有天

我这几个数可不一样，如果你能一次性取走某堆数就必胜我就佩服!否则.......


比如7，9，16你第一次怎么取？
还有13，20，200你又怎么取？
最后16，34，50你又怎么取？

哦，这个问题从小时候开始一直苦苦纠缠于我，今天我终于搞了个明白，虽然只知道做法不懂其意义，但还是值得欣慰!

上面三组用二进制的解法：
(1)7，9，16

    　　 1　1　1       =7
    　1　0　0　1       =9
+   1  0  0   0  0     =16
得 1  1  1   1   2

为使其得数都为偶数只好减少10000=16这个数，把它减少为1110=14
         1   1   1
     1  0   0   1
+   1  1   1   0

得 2   2   2   2   安全状态(也就是后手必胜)

所以7，9，16先手就取成7，9，14胜!

(2)13，20，200
是先手胜

   1   1   0  1     =13

+  1    0    1   0  0     =20

    *******************    =200(二进制用笔算太麻烦)

得  1    1   2   0  1

为使其得数都成偶数

所以       1    1   2   0   1

      +      1     1   0  0    1=25

得           2    2   2   0   2

先手把200取成25就必胜 (13 ， 20， 25)

(3)16，34，50

其得数都为偶数，所以16，34，50是先手必败。