兩人游戲： 給定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的證明).