(一)巴什博奕(Bash Game):

只有一堆n個(gè)物品,兩個(gè)人輪流從這堆物品中取物,規(guī)定每次至少取一個(gè),最多取m個(gè).最后取光者得勝.

顯然,如果n=m+1,那么由于一次最多只能取m個(gè),所以,無論先取者拿走多少個(gè),后取者都能夠一次拿走剩余的物品,后者取勝.因此我們發(fā)現(xiàn)了如何取勝的法則：如果n=(m+1)r+s,(r為任意自然數(shù),s≤m),那么先取者要拿走s個(gè)物品,如果后取者拿走k(≤m)個(gè),那么先取者再拿走m+1-k個(gè),結(jié)果剩下(m+1)(r-1)個(gè),以后保持這樣的取法,那么先取者肯定獲勝.總之,要保持給對(duì)手留下(m+1)的倍數(shù),就能最后獲勝.

這個(gè)游戲還可以有一種變相的玩法：兩個(gè)人輪流報(bào)數(shù),每次至少報(bào)一個(gè),最多報(bào)十個(gè),誰能報(bào)到100者勝.

(二)威佐夫博奕(Wythoff Game):

有兩堆各若干個(gè)物品,兩個(gè)人輪流從某一堆或同時(shí)從兩堆中取同樣多的物品,規(guī)定每次至少取一個(gè),多者不限,最后取光者得勝.

這種情況下是頗為復(fù)雜的.我們用(ak,bk)(ak ≤ bk ,k=0,1,2,...,n)表示兩堆物品的數(shù)量并稱其為局勢(shì),如果甲面對(duì)(0,0),那么甲已經(jīng)輸了,這種局勢(shì)我們稱為奇異局勢(shì).前幾個(gè)奇異局勢(shì)是：(0,0)、(1,2)、(3,5)、(4,7)、(6,10)、(8,13)、(9,15)、(11,18)、(12,20).

l         可以看出,a0=b0=0,ak是未在前面出現(xiàn)過的最小自然數(shù),而 bk= ak + k,奇異局勢(shì)有如下三條性質(zhì)：

1、任何自然數(shù)都包含在一個(gè)且僅有一個(gè)奇異局勢(shì)中.

由于ak是未在前面出現(xiàn)過的最小自然數(shù),所以有ak > ak-1 ,而 bk= ak + k > ak-1 + k-1 = bk-1 > ak-1 .所以性質(zhì)1.成立.

2、任意操作都可將奇異局勢(shì)變?yōu)榉瞧娈惥謩?shì).

事實(shí)上,若只改變奇異局勢(shì)(ak,bk)的某一個(gè)分量,那么另一個(gè)分量不可能在其他奇異局勢(shì)中,所以必然是非奇異局勢(shì).如果使(ak,bk)的兩個(gè)分量同時(shí)減少,則由于其差不變,且不可能是其他奇異局勢(shì)的差,因此也是非奇異局勢(shì).

3、采用適當(dāng)?shù)姆椒?/span>,可以將非奇異局勢(shì)變?yōu)槠娈惥謩?shì).

假設(shè)面對(duì)的局勢(shì)是(a,b),若 b = a,則同時(shí)從兩堆中取走 a 個(gè)物體,就變?yōu)榱似娈惥謩?shì)(0,0)；如果a = ak ,b > bk,那么,取走b - bk個(gè)物體,即變?yōu)槠娈惥謩?shì)；如果 a = ak , b < bk ,則同時(shí)從兩堆中拿走 ak – a[b – ak]個(gè)物體,變?yōu)槠娈惥謩?shì)( a[b – ak] , a[b – ak]+ b - ak)；如果a > ak ,b= ak + k,則從第一堆中拿走多余的數(shù)量a - ak 即可；如果a < ak ,b= ak + k,分兩種情況,第一種,a=aj (j < k),從第二堆里面拿走 b - bj 即可；第二種,a=bj (j < k),從第二堆里面拿走 b - aj 即可.

從如上性質(zhì)可知,兩個(gè)人如果都采用正確操作,那么面對(duì)非奇異局勢(shì),先拿者必勝；反之,則后拿者取勝.

l         那么任給一個(gè)局勢(shì)(a,b),怎樣判斷它是不是奇異局勢(shì)呢？我們有如下公式：

ak =[k(1+√5)/2], bk= ak + k (k=0,1,2,...,n 方括號(hào)表示取整函數(shù))

奇妙的是其中出現(xiàn)了黃金分割數(shù)(1+√5)/2 = 1.618...,因此,由ak,bk組成的矩形近似為黃金矩形,由于2/(1+√5)=(√5-1)/2,可以先求出j=[a(√5-1)/2],若a=[j(1+√5)/2],那么a = a[j],b[j] = a[j] + j,若不等于,那么a = a[j+1],b[j+1] = a[j+1]+ (j + 1),若都不是,那么就不是奇異局勢(shì).然后再按照上述法則進(jìn)行,一定會(huì)遇到奇異局勢(shì).

得勝.

(三)尼姆博奕(Nimm Game):

有三堆各若干個(gè)物品,兩個(gè)人輪流從某一堆取任意多的物品,規(guī)定每次至少取一個(gè),多者不限,最后取光者得勝.

這種情況最有意思,它與二進(jìn)制有密切關(guān)系,我們用(a,b,c)表示某種局勢(shì),首先(0,0,0)顯然是奇異局勢(shì),無論誰面對(duì)奇異局勢(shì),都必然失敗.第二種奇異局勢(shì)是(0,n,n),只要與對(duì)手拿走一樣多的物品,最后都將導(dǎo)致(0,0,0).仔細(xì)分析一下,(1,2,3)也是奇異局勢(shì),無論對(duì)手如何拿,接下來都可以變?yōu)?/span>(0,n,n)的情形.

計(jì)算機(jī)算法里面有一種叫做按位模2加,也叫做異或的運(yùn)算,我們用符號(hào)(+)表示這種運(yùn)算.這種運(yùn)算和一般加法不同的一點(diǎn)是1+1=0.先看(1,2,3)的按位模2加的結(jié)果：

1 =二進(jìn)制01

2 =二進(jìn)制10

3 =二進(jìn)制11 (+)

———————

0 =二進(jìn)制00 (注意不進(jìn)位)

對(duì)于奇異局勢(shì)(0,n,n)也一樣,結(jié)果也是0.

任何奇異局勢(shì)(a,b,c)都有a(+)b(+)c =0.

如果我們面對(duì)的是一個(gè)非奇異局勢(shì)(a,b,c),要如何變?yōu)槠娈惥謩?shì)呢？假設(shè) a < b< c,我們只要將 c 變?yōu)?/span> a(+)b,即可,因?yàn)橛腥缦碌倪\(yùn)算結(jié)果: a(+)b(+)(a(+)b)=(a(+)a)(+)(b(+)b)=0(+)0=0.要將c 變?yōu)?/span>a(+)b,只要從 c中減去 c-(a(+)b)即可.

可以推廣到：有n堆若干個(gè)物品,兩個(gè)人輪流從某一堆取任意多的物品,規(guī)定每次至少取一個(gè),多者不限,最后取光者得勝.