两人游戏： 给定K堆火柴，每堆火柴数为N1,N2,N3,...Nk,
两人轮流拿，看谁拿到最后一根火柴谁就胜利。
    规则：每次只能从一堆中拿，每次至少拿一根，最多可拿光。
假若我先走，求教我必胜的策略。
    比如：有三堆，1  2  3

---------------------------------------------------------------

求出 N = N1^N2^N3^…^Nk （“^”为C++中的按位异或运算符）。
若 N 等于零，称此状态为必胜状态，否则称为非必胜状态。
从必胜状态中改小一个且只改小一个数字是不可能到达另一个必胜状态的。
从非必胜状态中一定可以找到一个数n，使得n<Ni且N1^N2^…^Ni-1^n^Ni+1^…^Nk=0 (其中1<=i<=k)，也就是说从非必胜状态一定可以只改小一个数字而到达必胜状态。
若某一方保证每次拿火柴后当前状态都是必胜状态，此方将胜出（当然要求相对此方的初始状态为非必胜状态）。

---------------------------------------------------------------

发信人: Nature (成长●快乐●烦恼), 信区: Mathematics
标  题: 关于取火柴问题的解答
发信站: 南京大学小百合站 (Tue May  7 09:22:18 2002), 站内信件

题目1：    今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，
可将一堆全取走，但不可不取，最后取完者为胜，求必胜的方法。

题目2：    今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，
可将一堆全取走，但不可不取，最后取完者为负，求必胜的方法。

解答如下：

先解决第1题

定义1：若所有火柴数异或为0，则该状态被称为利他态，用字母T表示；否则，
为利己态，用S表示。

定理1：对任何S态，存在方法，从其中取一堆中的若干根，使状态变为T态。
引理1.1 ：A(i)为非副整数，i=1..n, 记c=A(1) xor A(2) xor ……  xor A(n),

若c>0,则存在A(t), A(t) xor c <A(t)
证明： 把c表示成二进制，记它的二进制数的最高位为第p位，
  则必然存在一个A(t),它二进制的第p位也是1。（否则，若所有的A(i)的第p位都是0，
c的第p位就也为0，矛盾！）
  x=a(t) xor c 的第p位将为1 xor 1,即0；
  又因为c的最高位为p，所以x高于p位的值不变。所以必有x<a(t).即a(t) xor 
c<a(t)
.
  命题得证。

再来证定理1.
证明：
 设共有n堆火柴，每堆的数目分别为A(i)，i=1..n，A(i)为非副整数.
 记c=A(1) xor A(2) xor ……  xor A(n),
 因为是S态，所以 c>0;
 所以存在A(t), A(t) xor c <A(t)。
 A(t)' = A(t) xor c <A(t)
  c' = A(1) xor A(2) xor …  xor A(t)' xor … xor A(n)
   = A(1) xor A(2) xor …  xor A(t) xor c xor … xor A(n)
   = A(1) xor A(2) xor …  xor A(t) xor … xor A(n) xor c
   = c xor c = 0
所以，用把第t堆由A(t)根取成A(t)' 根（A(t)' = A(t) xor c <A(t) )，状态成
为T态。
故命题成立。    #

定理2：T态，取任何一堆的若干根，都将成为S态。
证明：反证法：
  反设存在一堆，记为第m堆，从中取了若干根，根数由A(m)变为A(m)' .
  A(m)>A(m)' 状态均为T态。
  记c=A(1) xor A(2) xor … xor A(m) xor…  xor A(n),
  记c'=A(1) xor A(2) xor … xor A(m)' xor…  xor A(n),
  c=0;c'=0;
  所以有 0= A(1) xor A(2) xor … xor A(m) xor…  xor A(n)
= A(1) xor A(2) xor … xor A(m-1) xor A(m+1) xor… xor A(n) xor A(m)
= d xor A(m)
     d= A(1) xor A(2) xor … xor A(m-1) xor A(m+1) xor… xor A(n)
故 A(m)=d
        同理， d xor A(m)' =0
   A(m)'= d
  所以，A(m)'=A(m) . 矛盾！
  故反设不成立。原命题成立。 #

定理 3：S态，只要方法正确，必赢。
 最终胜利即由S态转变为T态，任何一个S态，只要把它变为T态，（由定理一，
可以把它变成T态。）对方只能把T态转变为S态(定理2)。这样，所有S态向T态的转变都可以
有己方控制，对方只能被动地实现由T态转变为S态。故S态必赢。 #
定理4：T态，只要对方法正确，必败。
 由定理3易得。


我们再来处理第2题。我们会发现两题会有一些相同之处，控制S->T态的人控制着
主动权
。经过分析，我们有以下结论：
定义2：若一堆中仅有1根火柴，则被称为孤单堆。若大于1根，则称为充裕堆。
定义3：T态中，若充裕堆的堆数大于等于2，则称为完全利他态，用T2表示；若充
裕堆的堆数等于0，则称为部分利他态，用T0表示。
定理4：不存在充裕堆数为1的T态。
证明：
 孤单堆的根数异或只会影响二进制的最后一位，但充裕堆会影响高位（非最后一位）。

 一个充裕堆，高位必有一位不为0，则所有根数异或不为0。故不会是T态。
定义4：S态中，若充裕堆的堆数大于等于2，则称为完全利己态，用S2表示；若充
裕堆的堆数等于1，则称为自主利己态，用S1表示; 若充裕堆的堆数等于0，则称为部分利
己态，用S0表示。

定理4：S0态，即仅有奇数个孤单堆，必败。T0态必胜。
证明：S0态，其实就是每次只能取一根。每次第奇数根都由己取，第偶数根都由对
方取，所以最后一根必己取。败。
  同理, T0态必胜#
定理5：S1态，只要方法正确，必胜。
证明：若此时孤单堆堆数为奇数，把充裕堆取完；否则，取成一根。
   这样，就变成奇数个孤单堆，由对方取。
   由定理4，对方必输。己必胜。 #
定理6：S2态不可转一次变为T0态。
证明：充裕堆数不可能一次由2变为0。得证。 #
定理7：S2态可一次转变为T2态。
证明：由定理1，S态可转变为T态，态可一次转变为T态
   又由定理6，S2态不可转一次变为T0态，
   所以转变的T态为T2态。 #
定理8：T2态，只能转变为S2态或S1态。
证明：. 由定理2，T态必然变为S态。
     由于充裕堆数不可能一次由2变为0，所以此时的S态不可能为S0态。
  命题得证。
定理9：S2态，只要方法正确，必胜.
证明：方法如下：
   1） S2态，就把它变为T2态。（由定理7）
   2） 对方只能T2转变成S2态或S1态(定理8)
  若转变为S2, 转向1）
  若转变为S1, 这己必胜。（定理5）
定理10：T2态必输。
证明：同9。
 综上所述，必输态有： T2,S0
     必胜态：   S2,S1,T0.
两题比较：
第一题的全过程其实如下：
 S2->T2->S2->T2-> …… ->T2->S1->T0->S0->T0->……->S0->T0(全0)
第二题的全过程其实如下：
 S2->T2->S2->T2-> …… ->T2->S1->S0->T0->S0->……->S0->T0(全0)
下划线表示胜利一方的取法。
    是否发现了他们的惊人相似之处。
我们不难发现(见加黑部分)，S1态可以转变为S0态（第二题做法），也可以转变为
T0（第一题做法）。哪一方控制了S1态，他即可以有办法使自己得到最后一根（转变为
T0）,也可以使对方得到最后一根（转变为S0）。
 所以，抢夺S1是制胜的关键！
 为此，始终把T2态让给对方，将使对方处于被动状态，他早晚将把状态变为S1.
(见定理9的证明).