就像物理的不共容原理一样，数学游戏的趣味性和其数学理论的完整性，成为互相排斥的两部份。一种游戏完全被数学决定以后，玩的人只要晓得其中的理论，无不处于优势。游戏本身则成为数学的计算，玩起来必索然无味；但如果将它视为数学问题处理，则蕴藏有甚多美妙的理论在其中。富有挑战性的游戏，则没有固定的规律可寻，必须随机应变，靠临场的机智和以往的经验取胜，玩者有味；但在数学理论上则没有什么可言。拈及其各种变型游戏大都属于前者。当做一种学问，我们只关心其富有趣味的数学理论。在所有双人对局游戏中，拈是极其古老且饶富兴趣的一个课题。据说，拈源自中国，经由被贩卖到美洲的奴工们外传。辛苦的工人们，在工作闲暇之余，用石头玩游戏以排遣寂寞。流传到高级人士，则用辨士(Pennils)，在酒吧柜台上玩。最有名的是将十二枚辨士分三列排成「三、四、五」的游戏，如下图：http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img1.gif游戏的规则很简单。两人轮流取铜板，每人每次需在某一列取一枚或一枚以上的铜板，但不能同时在两列取铜板，直到最后，将铜板拿光的人赢得此游戏。也可以做相反的规定：最后将铜板拿光的人输。一个头脑灵活的赌棍不久就会发现，先取的人，在第一列的三枚铜板中取走二枚，就能稳操胜算。一个显而易见的规律是，只要你留下两列枚数相同的铜板，必可获胜。在这里对称扮演极重要的角色。如果这个游戏只是「三、四、五」型态，那么不久后，大部份人就能熟悉其中规律，并且变得没有兴趣。有一个改变的方法是，将铜板的列数增加，每一列的枚数改变。这样的做法，的确使人有毫无规律的感觉，至少不至于像「三、四、五」型态的拈一样易于把握。直到本世纪初，哈佛大学数学系副教授查理士．理昂纳德．包顿(ChalesLeonardBouton)提出一篇极详尽的分析和证明，利用数的二进制表示法，解答了这个游戏的一般法则：对任意列数的铜板，每列有任意枚数，如何取得致胜之道？在包顿的术语中，拿过后剩下的残局不是安全(safe)就是不安全(unsafe)的局面。在所有安全的情况下，不管对方如何拿总是到一不安全的情况，你可以再取适当枚数的铜板（在适当的某一列），达到另一安全的情况，这样一直到拿光铜板为止，当然最后一次拿光铜板的一定是你。反之，你如果留下不安全的情况，对方必有方法在适当的某一列，取走适当枚数的铜板，达到他的安全情况，也就是说你输定了。包顿的方法很简单。首先，将各列铜板的枚数化成二进制数，相加，但不进位，然后再看和的各个位数。如果和的各个位数都是偶数，则表示一安全残局;否则，如果有一位是奇数，则为不安全残局。例如「三、四、五」游戏，一开始就是不安全残局，先拿的人可以适当取二枚而造成他的安全残局。另一个不安全残局的例子如下：或者为什么安全残局和不安全残局可以利用上述的方法判定呢？这个道理其实很简单。首先，如果将各列铜板数化为二进制表示法，相加，但不进位，得到的各个位数都是偶数的话，不论对方取那一列，多少枚铜板，则那一列铜板数所对应的二进制表示法中，必有某一位或数字由0变成1或者由1变成0，其相加的和也相对的有某一位或数字由偶数变成奇数。例如，{1,4,5}这个安全残局，从第二列的4枚铜板取走2枚，则http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img5.gifhttp://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img6.gif相反的，如果和的某一位或数字是奇数，则我们有办法在某一列取走适当枚数的铜板，使得新的和的各个位数都是偶数。首先，选取和中所有为奇数的各个位数http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img7.gif；例如在{14,15,18,22}的例子中和的第1和第3位是奇数。其次看这些位数中那一个是最左边一位；本例中当然是第3位。找某一列，使其二进制表示法在此位上刚好是1；本例中，可以找第一例的14，也可以找第二列的15。然后将此列的铜板数所对应的二进制数中，凡是第ai位，都改变其数值，亦即若为0则变为1，若为1则变为0，如此得到一新数，我们只要在此列铜板取走适当的数目，使达到这新的枚数，即可以使新的和的各个位数都是偶数；例如，若考虑第一列的14=1110枚铜板，将其第1和第3位改变得到1011=11枚铜板，所以要在第一列取走3枚铜板。相反规定，拿光铜板的人算输峙，只耍将上面的规律略加修饰，也可以控制局面。如果你一直拥有安全残局，对方一直处于不安全的情况，到某一时候，对方留下来的不安全残局一定会出现一种特殊型态，即是，除某一列铜板的枚数大于1，其它各列均只有一枚铜板（拿光的各列不管它），这时候你的拿法要开始注意，你需将较多枚铜板这一列全部取光，或者拿到只剩下一枚，决定采取何者，完全看你拿了之后，要能使剩下的列数为奇数，当然每一列均只有一枚铜板。显而易见的是，以后一人都取一列，也是一枚，到最后拿的一定是对方，于是你就赢了。有很多人把这个方法写成计算机程序，来和人对抗，不知就理的人被骗得团团转，无不惊叹计算机的神奇伟大。其实说穿了，只因为它计算比人快，数的转化为二进制元其速度快得非人能比，如此罢了。
用来玩拈的道具不限于铜板。工余之时，石头可以玩；无聊磕瓜子时，瓜子可以玩；围棋子可以玩……。也可以将石头分堆放置，一堆相当于一列。这些都不是重点，我们甚至可以改变取铜板的规定，最后取光时输赢的规定……，于是，各种不同的变型游戏遂产生。在拈的游戏中，如果只有两列铜板，则很容易看出来，留下两列枚数相同的铜板是致胜的安全残局。也就是我们一开始说的对称这个想法。事实上，包顿很巧妙的将对称化成二进制和的各个位数为偶数，将问题给一般化，这是很天才的想法。所以两列的拈是没有什么可说的。将拈的规定略加修改，成为只有两列的威氏游戏，却极其有意思。规定是这样的，铜板只有两列，每列的枚数随玩者任意规定，两人轮流取铜板，取的时候，需要任一列中取一枚或多枚铜板，或者同时在两列取同样枚数的铜板，直到最后将铜板取光的人赢。当然也可以像拈一样有相反的规定，最后将铜板取光的人输。今只讨论前者。拈的玩法完全不能适用于威氏游戏。所有拈的安全残局{n,n}，在威氏游戏中都是不安全残局。因为我们加了一个规定，可以从两列铜板中同时取相同枚数的铜板。[例3]若n是正整数，则{0,n}和{n,n}都是不安全残局。[例4]{1,2}是安全残局。因为http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img8.gif不管如何取，总是成为不安全残局。[例5]{3,5}是安全残局。因为http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img9.gif不管对方如何取，不是到达例3的不安全残局，就是你可以再适当取，使成例4的安全残局。继续推演下去，可以得到许多组安全残局{1,2},{3,5},{4,7},{6,10},…。一般而言，第n组安全残局{an,bn}可由下式定义得到(1)a1=1,b1=2。(2)若http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img10.gif已经求得，则定义an为未出现在以上这2n-2个数中的最小整数。(3)bn=an+n。做成表就是n12345678910an13468911121416bn25710131518202326由(1)、(2)、(3)所定义的二数列http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img11.gif和http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img12.gif，具有下列特性：(甲)数列http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img11.gif和http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img12.gif均是严格递增数列，而且bn=an+n。(乙)http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img13.gif,http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img14.gif其中N表示正整数的集合，http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img15.gif,http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img16.gif(丙)若{an,bn}={am,bm}，则n=m，即an=am,bn=bm。事实上，相反的，具有(甲)、(乙)性质的数列，也就是具有(1)、(2)、(3)性质的数列。[定理]{an,bn}是威氏游戏的安全残局，其余的组合{x,y}都是不安全残局。[证]我们只要证明下面二点即可。(1)由任何一组{an,bn}取铜板，不管如何取，都不会成为另一组{am,bm}。假设从一组{an,bn}中的an取x，bn取y而能达到另一组{am,bm}，则an-x=am，bn-y=bm。(i)当x=0，y>0时，an=am则n=m，得y=0，矛盾。(ii)当x>0，y=0时，bn=bm则n=m，得x=0，矛盾。(iii)当x=y>0时，m=bm-am=(bm+y)-(am+x)=bn-an=n，矛盾。(2)由任一组不是{an,bn}型的{x,y}可以适当取铜板使成某一组{am,bm}。为方便计，可假设y>=x。(i)当x为某个bm时，y-am=y-(bm-m)=(y-x)+m>0，可在y中取y-am，变成{bm,am}。(ii)当x为某个am，且y>bm时，在y中取y-bm，变成{am,bm}。(iii)当x为某个am，且http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img18.gif时，y-x0。在x中取x-ak，在y中取y-bk=x-ak则变成{ak,bk}。这个定理不但告诉我们{an,bn}是威氏游戏的安全残局，其证明过程更暗含从不安全残局取铜板变成安全残局的法则。我们只要记住这个法则，还有{an,bn}组合，则无不处于优势。但是有一个问题是，当数目很大的时候，要记住一大堆{an,bn}是一件非常吃力不讨好的工作。我们于是自然会问，有没有像拈类似的法则用来判断任何一组{x,y}是否为威氏游戏的安全残局，而不必逐一计算{a1,b1},{a2,b2}…。答案是有的，在解答这之前，我们需要谈谈费氏数列及相关的问题。
费氏数列是指无穷数列1,2,3,5,8,13,21,…而言，它的一般表示式是f0=1，f1=2，fn+2=fn+1+fn真正把它计算出来是http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img19.gif计算的过程和我们要讨论的没有太大关系，兹从略。有一点可以注意的是，{fn}几乎成一等比级数。因为http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img20.gif,http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img21.gif，其绝对值小于1，当n很大时，http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img22.gif变得很小，几乎可以省略不计。也就是说http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img23.gif，几乎是等比级数型式增加。费氏级数最有趣的特性是，自然界许多生长的过程或多或少和它有点关联。可参考《数学漫谈》第四章（下）。通常我们所熟悉的阿拉伯数字表示自然数的方法是利用0,1,2,3,4,5,6,7,8,9十个数字为基础，借「位」的观念，和「逢十进一」的方法组织而成。这就是十进制法。举例来说，345=3x102+4x101+5。仿照这个道理，有各种进位法，例如计算机所熟悉的二进制法，仅有0和1两种基本数字，10110表示1x24+0x23+1x22+1x21+0=16+4+2=22。八进位法，则仅有0,1,2,3,4,5,6,7八个数字。标准的进位法中，各位都是满一个固定数就进位。例如：十进制法是满十进一，即个位数满十进一到十位数，十位数满十进一到百位数，百位数满十进一到千位数，……等。考虑一个自然数的无穷数列B0,B1,B2,…其中B0=1，其余各Bn均大于1。我们可以采取一种名为B进位法的记数法则：由右边算起，第一位满B1进一到第二位，第二位满B2，进一到第三位，……，第n位满Bn，进一到第n+1位。任何一个自然数x可以有唯一的B进位表示法http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img24.gif，其中http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img25.gif。则http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img26.gif
标准十进制法是取Bi=10,i=1,2,…。各种k进位法是指Bi=k,i=1,2,…而言。[例6]Bn=n+1，求347的B进位表示法。http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img27.gif所以347=2x(2x3x4x5)+4x(2x3x4)+1x(2x3)+2x2+1=24121B假设Pn=B0B1…Bn则http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img28.gif成为一个以1为起点的严格递增无穷自然数列。自然数N的B进位表示法http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img29.gif如果我们一开始就取一个以1为起点的严格递增无穷自然数列http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img28.gif，对于任何自然数N表示成http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img30.gif,http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img31.gif有无困难？答案是有的。在B进位表示法中，每一个自然数恰有唯一的一种表示法；但是在这种新的表示法中，不一定每个自然数均只有一种表示法。[例6.1]数列http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img28.gif定义为Pn=2n+1,则http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img32.gif有趣的是，自然数的P数列表示法一定有解。[定理2]http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img28.gif是一个以1为起点的严格递增无穷自然数列，则每一自然数N至少可以表示成一种P数列表示法http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img33.gif[证]利用数学归纳法证明：N
n=1时，N=l0，其中l0(P)=N。若n=k时本定理成立，则n=k+1时，利用除法公式，可以找到lk及r使得http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img35.gif由归纳法假设http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img36.gif而且http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img31.gif。故http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img37.gif将上面这种理论用到费氏数列{fn}因为http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img38.gif，所以费氏表示法中的各个「位数」只能是0或1。费氏数列表示法不具有唯一性。[例7]化60为费氏数列表示法。n012345678fn1235813213455http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img39.gif因为fn+2=fn+1+fn，费氏数列表示法中有一种有趣的「进位法」：第n位和第n+1位都是1时，可以进位到第n+2位。如上例10110110(f)的第5和第6位都是1，故可以进位到第7位，将原数化成11000110(f)；同理，可将11000110(f)的第2和第3位进位到第4位，成为11001000(f)。利用这个性质，在一数的某一费氏数列表示法中，如果有相邻的两位均是1，则可以进位到左边一位，化成另一个不同的表示法，继续化简，到最后，可以得到一种表示法，其中li各数目，相邻两个不同时为1（否则，再进位即可），每一个数都有一种唯一的如此表示法，称之为标准表示法。另一有趣的性质是：如果lnln-1…l1l0(f)中各位数字0和1相间出现，例如101010(f)或10101(f)则http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img40.gif
现在回到第(二)节的数列{an}和{bn}。一个相当有趣的事实是，如果将威氏游戏的各组安全残局{an,bn}用费氏数列标准表示法表示出来，如下表：http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img41.gif仔细观察，各个bn恰好是an后面加一个0，每个an最右边有偶数个连续的0（包括没有0），当然bn最右边有奇数个连续的0。有了这个结果，我们要检查一组{x,y}（其中x<=y）是否安全残局，就可以将x和y表成费氏数列标准表示法，再看看是否合于上述的条件即可。这中间的优点是，我们不必再计算所有http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img43.gif的安全残局{an,bn}，以决定{x,y}是否安全。更重要的是，我们将有一种简便的方法，可以将不安全残局{x,y}适当的取成某一安全残局{an,bn}。当然，数论上的一些结果告诉我们http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img44.gif,http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img45.gif,（[x]表示小于或等于x的最大整数，例如[2.99]=[2.0]=[2]=2）由定理1，我们几乎要求出2x/(sqrt5-1)组{an,bn}才能顺利的判定安全残局，以及由不安全残局拿成安全残局的方法。当x大的时候，这么多的数据处理起来必然不方便。上述{an,bn}的性质，只是依观察而得，现在我们要证明其真实性。我们所以要这样做，不光是因为数学上的严密性，在证明的过程中，用到的一些计算，将很有用处。首先将自然数分成A和B两部份，A是所有费氏标准表示法中右边有偶数个连续0的自然数的集合，B则是所有费氏漂准表示法中右边有奇数个连续0的自然数的集合。将A中之数由小而大排成一数列http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img46.gif设bn''是an''费氏标准表示法右边再加一个0者。我们将证明http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img47.gif且合于第(二)节的(甲)(乙)条件。所以，事实上就是http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img48.gif因此证明了上述的性质。(乙)易于知道成立。因为http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img46.gif和http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img49.gif都是严格增加数列，为了证明(甲)，我们只要证明bn''=an''+n就可以，兹分下面两步骤，证明之。(第一)bn''-an''，随n增加而增加。也就是，当n>m时，bn''-an''>bm''-am''。[证]假设http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img50.gif
上面均是标准表示法，但左边有的填0（即lr或http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img51.gif可能为0...等）以便对齐。n>m表示an''>am''，也就是有一个ss成立，http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img54.gif。因为http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img55.gif可见bn''-an''>bm''-am''(第二)对于任一自然数x，有一组{an'',bn''}使得bn''=an''+x。[证]当x的费氏标准表示法右边有奇数个连续的0时，取an''=x0(f),bn''=x00(f)即可以。当x的费氏标准表示法右边有偶数个连续的0时，即http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img56.gif取http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img57.gif利用http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img58.gif可见bn''=an''+x成立。(第一)和(第二)证明了bn''=an''+n的确成立。上面的证明不但说明了{an,bn}具有所述的性质，即是an为第n个费氏标准表示法之最右边有偶数个连续0的自然数，bn是第n个费氏标准表示法之最右边有奇数个连续0的自然数，尤有进者，bn的表示法等于an表示法右边再加一个0而已。而且由(第二)可以知道，对于任何一个自然数x，不必用归纳法从a1,b1,a2,b2,…算起，一直求至ax,bx。直接就可以算出ax和bx来。所以在利用定理1的时候，我们就可以不必记忆一大堆{an,bn}值了。
在所有拈的变型游戏中，单堆游戏似乎是比较简单的。最常见而为大众熟悉的玩法是这样的：「两人轮流取一堆石头，每人每次最少取1个，最多取k个，最后取光石头的人赢得此游戏。」请问有何致胜之道？和前面一样，所有的情况，可以分为安全和不安全两种。在这里k+1这个数扮演着极重要的角色，因为每次某一人拿的石头数i，合于1<=i=1，则fn2+kn+1分解http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img75.gif其中t为>=3为奇数，而且kn-t=kn+1或1+kn+1。http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img77.gif所以你可以取走y''个石头，使剩下http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img78.gif个石头，而且2y''<2fkn-t
(iii)双倍游戏中的安全残局是fn,n=1,2,…。[证明]x=fn时就如(ii)所述，对方所取的石头不超过http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img79.gif，所以你是留下安全残局。若一开始x不是fn型态，化为费氏标准式，http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img80.gif对方可以取去fkm剩下http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img81.gif；轮到你时不得取超过http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img82.gif，由(ii)可知他留下了他的安全残局，所以一开始是你的不安全残局。
有兴趣吗？让我们随便规定一个玩法：「一堆石头有100个，两人轮流取石，每次每人至少取一个，最多取上次对方取走石数的三倍。最后取光的赢得游戏。当然，第一个拿的人不可以第一次就取光所有石头。」数学传播杂志（有很多有意思的数学问题，属于科普杂志）http://www.math.sinica.edu.tw/media/default.jsp
http://www.mydrs.org2005-1-9大榕树博弈是信息学和数学试题中常会出现的一种类型，算法灵活多变是其最大特点，而其中有一类试题更是完全无法用常见的博弈树来进行解答。寻找必败态即为针对此类试题给出一种解题思路。此类问题一般有如下特点：1、博弈模型为两人轮流决策的非合作博弈。即两人轮流进行决策，并且两人都使用最优策略来获取胜利。2、博弈是有限的。即无论两人怎样决策，都会在有限步后决出胜负。3、公平博弈。即两人进行决策所遵循的规则相同。以下题目都属于这一类：POJ1740ANewStoneGame
MIPT100NimGame--whoisthewinner?
POJ1704GeorgiaandBobPOJ1067取石子游戏本着先理论后实践的原则，本文先对“寻找必败态”做出理论上的解释：要理解这种思想，首先要明白什么叫必败态。说简单点，必败态就是“在对方使用最优策略时，无论做出什么决策都会导致失败的局面”。其它的局面称为胜态，值得注意的是在胜态下做出错误的决策也有可能导致失败。此类博弈问题的精髓就是让对手永远面对必败态。必败态和胜态有着如下性质：1、若面临末状态者为获胜则末状态为胜态否则末状态为必败态。2、一个局面是胜态的充要条件是该局面进行某种决策后会成为必败态。3、一个局面是必败态的充要条件是该局面无论进行何种决策均会成为胜态这三条性质正是博弈树的原理，但博弈树是通过计算每一个局面是胜态还是必败态来解题，这样在局面数很多的情况下是很难做到的，此时，我们可以利用人脑的推演归纳能力找到必败态的共性，就可以比较好的解决此类问题了。下面就通过实际题目来做一些分析：例1POJ1740ANewStoneGame题目大意是：有N堆石子，两人轮流进行操作，每一次为“操作者指定一堆石子，先从中扔掉一部分（至少一颗，可以全部扔掉），然后可以将该堆剩下的石子中的任意多颗任意移到其它未取完的堆中”，操作者无法完成操作时为负。分析：只有一堆时先手必胜。有两堆时若两堆相等则后手只用和先手一样决策即可保证胜利，后手必胜。若不同则先手可以使其变成相等的两堆，先手必胜。有三堆时先手只用一次决策即可将其变成两堆相等的局面，先手必胜。有四堆时由于三堆必胜，无论先手后手都想逼对方取完其中一堆，而只有在四堆都为一颗时才会有人取完其中一堆，联系前面的结论可以发现，只有当四堆可以分成两两相等的两对时先手才会失败。分析到这里，题目好象已经有了一些眉目了，凭借归纳猜想，我们猜测必败态的条件为“堆数为偶数（不妨设为2N），并且可以分为两两相等的N对”。下面只需证明一下这个猜想。其实证明这样的猜想很简单，只用检验是否满足必败态的三条性质即可。首先，末状态为必败态，第一条性质符合。其次，可以证明任何一个胜态都有策略变成必败态（分奇数堆和偶数堆两种情况讨论）。最后，证明任何一个必败态都无法变成另一个必败态（比较简单）。由于篇幅关系，这里就不具体证明了，如果有兴趣可以自己试试∶Ｐ接下来的程序就相当简单了，只用判断一下即可。有些题则比这一题的条件隐蔽许多，例如：例2MIPT100NimGame--whoisthewinner?题目大意是：有N堆石子，两人轮流取，每次可以从任意一堆中取任意多颗（但至少一颗），谁先取完谁胜。分析：还是用按照“手推小资料=〉猜想=〉证明”的模式。一堆时先手必胜。两堆时若两堆相等则先手必败，否则先手胜。三堆的情况就有点复杂了，此时，我们只好借助博弈树来在小范围内求解，从这些解中我们可以看出，对于由两个不同数字构成的两元组，都有且仅有一个三元必败态包含它，这又意味着什么呢？我们定义一个函数F(a,b)，表示“包含a,b的三元必败态中的第三数”，则有F(1,2)=3,F(1,3)=2,F(1,4)=5,F(1,5)=4,F(1,6)=7,F(1,7)=6...F(2,1)=3,F(2,3)=1,F(2,4)=6,F(2,5)=7,F(2,6)=4,F(2,7)=5...F(3,1)=2,F(3,2)=1,F(3,4)=7,F(3,5)=6,F(3,6)=5,F(3,7)=4.......................................................................................................................................................................敏锐的选手马上会发现，这个F(a,b)不就是aXORb的结果么？做到这里，答案就在眼前了，''XOR''运算恐怕就是本题的关键。继续求出一些四元必败态，这个性质仍然符合，于是我们猜想，必败态即为“所有堆的石子数XOR运算后结果为零的局面”。这也解释了为什么一堆石子必胜，两堆石子仅在相等时必败。接下来又是证明：依旧判断是否符合三条性质。第一条第三条显然满足，关键就是第二条。必胜态下，设所有堆石子XOR后结果为N，将其写成二进制，则至少有一堆石子写成二进制后在N的最高位上为一，则可以证明从这堆石子中取可以变成必败态，这里还是留给有兴趣的选手:)这一题就明显没有上一题轻松了，而且这是个经典问题，结论可以记下来。下面这个例子就是例2的强化版：例3POJ1704GeorgiaandBob题目大意是：一个1M的棋盘上有N个棋子，初始位置一定，两人轮流操作，每次移动一枚棋子，要求只能向左移且至少移动一格，而且不能到达或经过以前有棋子的格子，谁无法移动棋子就算输。分析：乍一看这一题棋子移动还要受其它棋子的限制，好象无法求出通解，但仔细分析会发现别有洞天。一个棋子每一次向左移的最大步数是固定的，而且随着移动减少，不是和取石子很像么？那么和取石子的区别在哪呢？就在于每一次移动时都会让右边相邻的那颗棋子移动空间变大，这样就和取石子只减不增有所不同了，我们应该怎样解决这个问题呢？我们并不放弃将其与我们熟悉的取石子对应，但我们将策略做小小的变动：将棋子从右端向左端每相邻两个分为一对，如果只剩一个就将棋盘左端加一格放一颗棋子与之配对，这样配对后好象和以前没有什么区别，但决策时就方便多了，因为我们大可不必关心组与组之间的距离，当对手移动一组中靠左边的棋子时，我们只需将靠右的那一颗移动相同步数即可！同时我们把每一组两颗棋子的距离视作一堆石子，在对手移动两颗棋子中靠右的那一颗时，我们就和他玩取石子游戏，这样就把本题与取石子对应上了。本例说明有许多模型看似复杂，但经过一些巧妙的变换，便可以转化成一些我们熟悉的模型，同时也充分体现了博弈的灵活。如果说前面的例子是介绍这种思想的运用的话，下面的方法就是讲这种思路的优越性了，因为这一题并不是走的“手推小资料=〉猜想=〉证明”的老路，而是直接利用性质推导必败条件。例4POJ1067取石子游戏题目大意是：......题目本来就是中文的-_-b。分析：刚拿到这一题时，我不加思索的猜想必败态为“两堆石子的数目是2：1”，用性质判定：第一条显然符合，第二条分情况讨论每一种“胜态”都有一种固定的方法变成“必败态”，再看第三条，设第一堆有N颗，第二堆有2N颗，则无论怎样拿都无法让第二堆保持为第一堆的两倍。证毕。本以为此题就这么简简单单完了，但是我突然发现，当第一堆2颗，第二堆4颗时，从第二堆中取出3颗石子的话第二堆的确无法保持为第一堆的两倍，但第一堆会变成第二堆的两倍，基于此，整个猜想被彻底推翻。于是我反转思路，干脆从性质入手。我们令必败二元组为（a,b)形式，并令a<根据性质三，有这样两个推论：>a2,b1<>b2,a1<>b2,a2<>b1。推论二：对于任意两个的必败二元组(a1,b1)，(a2,b2)，有b1-a1<>b2-a2。利用性质和该推论，我们证明如下结论：“将必败二元组按首元为关键词排序，每个必败二元组中首元为未在前面的必败二元组中出现的最小正整数，并且第N组中两个数差为N”。利用数学归纳法证明：第一组为(1，2)，满足题意。若前N组满足题意，则有：设为在前N组中出现的最小正整数为M，则对于二元组（M，M+N+1）有：如果从数量为M的堆中取了石子，不妨设变成了(K,L)，则L-K>N，这样就有一个包含K，且不与前面N组任何一组相同的二元组，根据推论一，这个二元组一定不是必败二元组。如果只从数量为M+N+1的堆中取，不妨设剩下K颗，又分三种情况：K>M，则N+1>K-M>0，根据推论二，这个二元组一定不是必败二元组。K=M或0，显然不是必败二元组。0<综上，根据性质三，（M，M+N+1）为必败二元组，又根据排序的法则，（M，M+N+1）一定是数列的第（N+1）项。证毕。>从上面的例子可以看出，利用寻找必败态的思路解题对猜想和数学证明的能力要求很高，对思维的训练有很大好处，同时编程复杂度相当低，也不失为一种好的解题方法。
"上面均是标准表示法，但左边有的填0,以便对齐。n>m表示an''>am''，也就是有一个ss成立，l(s)>l''(s)。因为"下面应该是b(n)-a(n)=l(r)f(r-1)+l(r-1)f(r-2)+....+l(0)而不是b(n)-a(n)=l(r)f(r)+l(r-1)f(r-1)+...+l(0)
|
|
