威佐夫博奕(Wythoff Game):

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

這種情況下是頗為復(fù)雜的.我們用(ak,bk)(ak ≤ bk ,k=0,1,2,...,n)表示兩堆物品的數(shù)量并稱其為局勢,如果甲面對(0,0),那么甲已經(jīng)輸了,這種局勢我們稱為奇異局勢.前幾個奇異局勢是：(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,奇異局勢有如下三條性質(zhì)：

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

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

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

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

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

假設(shè)面對的局勢是(a,b),若 b = a,則同時從兩堆中取走 a 個物體,就變?yōu)榱似娈惥謩?/span>(0,0)；如果a = ak ,b > bk,那么,取走b - bk個物體,即變?yōu)槠娈惥謩荩蝗绻?/span> a = ak , b < bk ,則同時從兩堆中拿走 ak - ab - ak個物體,變?yōu)槠娈惥謩?/span>( ab - ak , ab - 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ì)可知,兩個人如果都采用正確操作,那么面對非奇異局勢,先拿者必勝；反之,則后拿者取勝.

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

ak =[k(1+√5)/2], bk= ak + k (k=0,1,2,...,n 方括號表示取整函數(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),若都不是,那么就不是奇異局勢.然后再按照上述法則進行,一定會遇到奇異局勢.
摘自（http://hi.baidu.com/zhulei632/blog/item/657efefaf299b1dbb58f3152.html）

poj 1067 有奇異局勢的判斷