兩人游戲： 給定K堆火柴，每堆火柴數(shù)為N1,N2,N3,...Nk,
兩人輪流拿，看誰拿到最后一根火柴誰就勝利。
    規(guī)則：每次只能從一堆中拿，每次至少拿一根，最多可拿光。
假若我先走，求教我必勝的策略。
    比如：有三堆，1  2  3

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

求出 N = N1^N2^N3^…^Nk （“^”為C++中的按位異或運(yùn)算符）。
若 N 等于零，稱此狀態(tài)為必勝狀態(tài)，否則稱為非必勝狀態(tài)。
從必勝狀態(tài)中改小一個(gè)且只改小一個(gè)數(shù)字是不可能到達(dá)另一個(gè)必勝狀態(tài)的。
從非必勝狀態(tài)中一定可以找到一個(gè)數(shù)n，使得n<Ni且N1^N2^…^Ni-1^n^Ni+1^…^Nk=0 (其中1<=i<=k)，也就是說從非必勝狀態(tài)一定可以只改小一個(gè)數(shù)字而到達(dá)必勝狀態(tài)。
若某一方保證每次拿火柴后當(dāng)前狀態(tài)都是必勝狀態(tài)，此方將勝出（當(dāng)然要求相對此方的初始狀態(tài)為非必勝狀態(tài)）。

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

發(fā)信人: Nature (成長●快樂●煩惱), 信區(qū): Mathematics
標(biāo)  題: 關(guān)于取火柴問題的解答
發(fā)信站: 南京大學(xué)小百合站 (Tue May  7 09:22:18 2002), 站內(nèi)信件

題目1：    今有若干堆火柴，兩人依次從中拿取，規(guī)定每次只能從一堆中取若干根，
可將一堆全取走，但不可不取，最后取完者為勝，求必勝的方法。

題目2：    今有若干堆火柴，兩人依次從中拿取，規(guī)定每次只能從一堆中取若干根，
可將一堆全取走，但不可不取，最后取完者為負(fù)，求必勝的方法。

解答如下：

先解決第1題

定義1：若所有火柴數(shù)異或?yàn)?，則該狀態(tài)被稱為利他態(tài)，用字母T表示；否則，
為利己態(tài)，用S表示。

定理1：對任何S態(tài)，存在方法，從其中取一堆中的若干根，使?fàn)顟B(tài)變?yōu)門態(tài)。
引理1.1 ：A(i)為非副整數(shù)，i=1..n, 記c=A(1) xor A(2) xor ……  xor A(n),

若c>0,則存在A(t), A(t) xor c <A(t)
證明： 把c表示成二進(jìn)制，記它的二進(jìn)制數(shù)的最高位為第p位，
  則必然存在一個(gè)A(t),它二進(jìn)制的第p位也是1。（否則，若所有的A(i)的第p位都是0，
c的第p位就也為0，矛盾！）
  x=a(t) xor c 的第p位將為1 xor 1,即0；
  又因?yàn)閏的最高位為p，所以x高于p位的值不變。所以必有x<a(t).即a(t) xor 
c<a(t)
.
  命題得證。

再來證定理1.
證明：
 設(shè)共有n堆火柴，每堆的數(shù)目分別為A(i)，i=1..n，A(i)為非副整數(shù).
 記c=A(1) xor A(2) xor ……  xor A(n),
 因?yàn)槭荢態(tài)，所以 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ài)成
為T態(tài)。
故命題成立。    #

定理2：T態(tài)，取任何一堆的若干根，都將成為S態(tài)。
證明：反證法：
  反設(shè)存在一堆，記為第m堆，從中取了若干根，根數(shù)由A(m)變?yōu)锳(m)' .
  A(m)>A(m)' 狀態(tài)均為T態(tài)。
  記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) . 矛盾！
  故反設(shè)不成立。原命題成立。 #

定理 3：S態(tài)，只要方法正確，必贏。
 最終勝利即由S態(tài)轉(zhuǎn)變?yōu)門態(tài)，任何一個(gè)S態(tài)，只要把它變?yōu)門態(tài)，（由定理一，
可以把它變成T態(tài)。）對方只能把T態(tài)轉(zhuǎn)變?yōu)镾態(tài)(定理2)。這樣，所有S態(tài)向T態(tài)的轉(zhuǎn)變都可以
有己方控制，對方只能被動地實(shí)現(xiàn)由T態(tài)轉(zhuǎn)變?yōu)镾態(tài)。故S態(tài)必贏。 #
定理4：T態(tài)，只要對方法正確，必?cái)　?
 由定理3易得。


我們再來處理第2題。我們會發(fā)現(xiàn)兩題會有一些相同之處，控制S->T態(tài)的人控制著
主動權(quán)
。經(jīng)過分析，我們有以下結(jié)論：
定義2：若一堆中僅有1根火柴，則被稱為孤單堆。若大于1根，則稱為充裕堆。
定義3：T態(tài)中，若充裕堆的堆數(shù)大于等于2，則稱為完全利他態(tài)，用T2表示；若充
裕堆的堆數(shù)等于0，則稱為部分利他態(tài)，用T0表示。
定理4：不存在充裕堆數(shù)為1的T態(tài)。
證明：
 孤單堆的根數(shù)異或只會影響二進(jìn)制的最后一位，但充裕堆會影響高位（非最后一位）。

 一個(gè)充裕堆，高位必有一位不為0，則所有根數(shù)異或不為0。故不會是T態(tài)。
定義4：S態(tài)中，若充裕堆的堆數(shù)大于等于2，則稱為完全利己態(tài)，用S2表示；若充
裕堆的堆數(shù)等于1，則稱為自主利己態(tài)，用S1表示; 若充裕堆的堆數(shù)等于0，則稱為部分利
己態(tài)，用S0表示。

定理4：S0態(tài)，即僅有奇數(shù)個(gè)孤單堆，必?cái)　0態(tài)必勝。
證明：S0態(tài)，其實(shí)就是每次只能取一根。每次第奇數(shù)根都由己取，第偶數(shù)根都由對
方取，所以最后一根必己取。敗。
  同理, T0態(tài)必勝#
定理5：S1態(tài)，只要方法正確，必勝。
證明：若此時(shí)孤單堆堆數(shù)為奇數(shù)，把充裕堆取完；否則，取成一根。
   這樣，就變成奇數(shù)個(gè)孤單堆，由對方取。
   由定理4，對方必輸。己必勝。 #
定理6：S2態(tài)不可轉(zhuǎn)一次變?yōu)門0態(tài)。
證明：充裕堆數(shù)不可能一次由2變?yōu)?。得證。 #
定理7：S2態(tài)可一次轉(zhuǎn)變?yōu)門2態(tài)。
證明：由定理1，S態(tài)可轉(zhuǎn)變?yōu)門態(tài)，態(tài)可一次轉(zhuǎn)變?yōu)門態(tài)
   又由定理6，S2態(tài)不可轉(zhuǎn)一次變?yōu)門0態(tài)，
   所以轉(zhuǎn)變的T態(tài)為T2態(tài)。 #
定理8：T2態(tài)，只能轉(zhuǎn)變?yōu)镾2態(tài)或S1態(tài)。
證明：. 由定理2，T態(tài)必然變?yōu)镾態(tài)。
     由于充裕堆數(shù)不可能一次由2變?yōu)?，所以此時(shí)的S態(tài)不可能為S0態(tài)。
  命題得證。
定理9：S2態(tài)，只要方法正確，必勝.
證明：方法如下：
   1） S2態(tài)，就把它變?yōu)門2態(tài)。（由定理7）
   2） 對方只能T2轉(zhuǎn)變成S2態(tài)或S1態(tài)(定理8)
  若轉(zhuǎn)變?yōu)镾2, 轉(zhuǎn)向1）
  若轉(zhuǎn)變?yōu)镾1, 這己必勝。（定理5）
定理10：T2態(tài)必輸。
證明：同9。
 綜上所述，必輸態(tài)有： T2,S0
     必勝態(tài)：   S2,S1,T0.
兩題比較：
第一題的全過程其實(shí)如下：
 S2->T2->S2->T2-> …… ->T2->S1->T0->S0->T0->……->S0->T0(全0)
第二題的全過程其實(shí)如下：
 S2->T2->S2->T2-> …… ->T2->S1->S0->T0->S0->……->S0->T0(全0)
下劃線表示勝利一方的取法。
    是否發(fā)現(xiàn)了他們的驚人相似之處。
我們不難發(fā)現(xiàn)(見加黑部分)，S1態(tài)可以轉(zhuǎn)變?yōu)镾0態(tài)（第二題做法），也可以轉(zhuǎn)變?yōu)?
T0（第一題做法）。哪一方控制了S1態(tài)，他即可以有辦法使自己得到最后一根（轉(zhuǎn)變?yōu)?
T0）,也可以使對方得到最后一根（轉(zhuǎn)變?yōu)镾0）。
 所以，搶奪S1是制勝的關(guān)鍵！
 為此，始終把T2態(tài)讓給對方，將使對方處于被動狀態(tài)，他早晚將把狀態(tài)變?yōu)镾1.
(見定理9的證明).