威佐夫博弈與貝蒂定理

1、威佐夫博弈威佐夫博弈(Wythoffs game ):有兩堆各若干個物品，兩個人輪流從某一堆取至少一個或同時從兩堆中取同樣多的物品，規(guī)定每次至少取一個，多者不限，最后取光者得勝。這種情況下是頗為復雜的。我們用(ak，bk)( ak ak-1,而bk= ak + k ak-1 + k ak-1 + k - 1 = bk-1 ak-1。所以性質(zhì)1成立。2。任意操作都可將奇異局勢變?yōu)榉瞧娈惥謩荨Ｊ聦嵣?，若只改變奇異局?ak, bk)的某一個分量，那么另一個分量不可能在其他奇異局勢中，所以必然是 非奇異局勢。如果使(ak, bk)的兩個分量同時減少，則由于其差不變，且不可能是其他奇異局勢的差，因此

2、也是非奇異局勢。3。采用適當?shù)姆椒?，可以將非奇異局勢變?yōu)槠娈惥謩?。假設(shè)面對的局勢是(a,b )，若b = a,則同時從兩堆中取走a個物體，就變?yōu)榱似娈惥謩?0 ,0 );如果a = ak, b bk那么，取走b - bk個物體，即變?yōu)槠娈惥謩?；如果a = ak , b ak, b= ak + k則從第一堆中拿走多余的數(shù)量a - ak即可;如果a ak ,b= ak + k分兩種情況，第一種 明aj (j k)從第二堆里面拿走b - bj即可；第二種，a=bj (j k)從第二堆里面拿走b - aj即可。詳細的證明過程：方法一簡單分析一下溶易知道兩堆石頭地位是一樣的，我們用余下的石子數(shù)(a,b)

3、來表示狀態(tài)，并畫在平面直角坐標系上。 用之前的定理：有限個結(jié)點的無回路有向圖有唯一的核中所述的方法尋找必敗態(tài)。先標出(0,0)，然后劃去所有(0,k),(k,0),(k,k)的格點；然后找y上方未被劃去的格點，標出(1,2),然后劃去(1,k),(k,2),(1+k,2 + k)，同時標出對 稱點(2,1)，劃去(2,k),(1,k),(2 + k,1+k);然后在未被劃去的點中在y=x上方再找出(3,5)。按照這樣的方法做下 去，如果只列出a = b的必敗態(tài)的話，前面的一些是(0,0),(1,2),(3,5),(4,7),(6,10),.接下來就是找規(guī)律的過程了，可能很辛苦，但是我寫得也不容

4、易，而且我暫時沒有看到其他地方有這樣的證明過程。 忽略(0,0)，記第n組必敗態(tài)為(an,bn)命題一 ：an + 1二前n組必敗態(tài)中未出現(xiàn)過的最小正整數(shù)分析：如果an+1不是未出現(xiàn)的數(shù)中最小的，那么可以從an+1的狀態(tài)走到一個使an + 1更小的狀態(tài)，和我們 的尋找方法矛盾。命題二：bn=an + n分析：歸納法：若前k個必敗態(tài)分別為(ak,ak + k),下證：第k+1個必敗態(tài)為(ak+1,ak+1 + k+1)從該第k+1個必敗態(tài)出發(fā)，一共可能走向三類狀態(tài)，從左邊堆拿走一些，從右邊堆拿走一些，或者從兩堆中拿走 一些.下面證明這三類都是勝態(tài).情況一：由命題一，任意一個比ak+1小的數(shù)都在之

5、前的必敗態(tài)中出現(xiàn)過，一旦把左邊堆拿少了，我們只要再拿 成那個數(shù)相應(yīng)的必敗態(tài)即可。情況二(從右邊堆拿走不太多)：這使得兩堆之間的差變小了，比如拿成了(ak+1,ak+1 + m),則可再拿成 (am,am + m)；情況二(從右邊堆拿走很多)：使得右邊一堆比左邊一堆更少，這時類似于情況一，比如拿成T(ak+1,am)(其 中 amak+1)，則可再拿成(am + m,am)；情況三：比如拿成(am,am + k+1)，則可再拿成(am,am + m).綜上所述，任何從(ak+1,ak+1 + k+1)出發(fā)走向的狀態(tài)都可以走回核中.故原命題成立.以上兩個命題對于確定(an,bn)是完備的了，給定(

6、0,0)然后按照這兩個命題，就可以寫出(1,2),(3,5),(4,7),.這樣我們得到了這個數(shù)列的遞推式，以下我們把這兩個命題當成是(3間血)的定義。先證明兩個性質(zhì)：性質(zhì)一：核中的an,bn遍歷所有正整數(shù)。分析:由命題一，二可得an,bn是遞增的，且由an的定義顯然。性質(zhì)二：A=an:n=123,.,B=bn:n = 1,23.，則集合 A,B 不交。分析：由核是內(nèi)固集，顯然?？吹竭@里大家有沒有想到Beatty序列呢，實際上an和bn就是一個Beatty序列。an = an,bn=pn,有 an + n=(a+1)n二甲n,解方程 1/(a+1) + 1/a=1得a=(sqrt5+1)/2，

7、到此，我們找到了該必敗態(tài)的通項公式。實際上這組Beatty序列還有一些別的性質(zhì)，比如當一個數(shù)是Fibonacc i數(shù)的時候，另一個數(shù)也是Fibonacc i數(shù)； 而且兩者的比值也越來越接近黃金比，這些性質(zhì)在得到通項公式之后不難證明。總的來說，這個問題給我們了哪些啟示呢？首先用定理所說的方法找核，然后給出核的規(guī)律(遞推，或是通項)并 且證明。方法二定理0:一個狀態(tài)是必敗態(tài)，當且僅當它的所有后繼狀態(tài)都是必勝態(tài)；而一個狀態(tài)是必勝態(tài)，只要它的后繼狀態(tài)有 一個以上的必敗態(tài)即可。證明略去。容易發(fā)現(xiàn)下面的定理：定理1 ：(a,b)和(b, a)的勝負性是相同的(a b)。證明：如果(a, b)是必勝態(tài)，那么

8、將必勝策略中所有的操作，對第一堆的變?yōu)榈诙?，對第二堆的變?yōu)榈谝欢?，就?gòu)成(b, a)的必勝策略定理2 ：若(a, b)是必敗態(tài)，則對于所有的x a和y b,(x, b)和(a, y)是必勝態(tài)。證明：對于x a和y b,不管是哪一種情況，總可以從x堆或y堆中取出一定量的石子使當前狀態(tài)變?yōu)楸財B(tài)(a, b)，由定理1 , (x, b)和(a, y)為必勝態(tài)。對于x a和y 0,(a + d, b + d)是必勝態(tài)。證明：與定理2類似。定理4:在所有的必敗態(tài)中，每個數(shù)字恰巧出現(xiàn)一次。證明：有了定理1,對于對稱的狀態(tài)我們只需要處理其中一個，而兩個數(shù)不會相同(相同的狀態(tài)必然是必勝態(tài))，于是我 們把每個

9、狀態(tài)中較小的數(shù)字放在前面，每行寫一個狀態(tài)，去掉括號并按照升序排列每行的第一個數(shù)，就構(gòu)成了如下 的矩陣：1 2576 10假設(shè)數(shù)字1在矩陣中出現(xiàn)兩次或兩次以上，則有(k,a), (k,b)都為必敗態(tài)，與定理2矛盾。假設(shè)數(shù)字10)，則對任意i,必然存在j(0jk)使得 (k-j,k+i-j)或(k,k+i-j)或(k-j,k+i)為必敗態(tài)(若不如此，則無論如何取石子，對方必勝)，根據(jù)假設(shè)，顯然(k,k+i-j)必 勝，因此，對任意 i,必有(k-j,k+i-j)或(k-j,k+i)=0, (0jk)必敗根據(jù)鴿巢原理，必然存在3個i的取值(其實是無窮多個，j只有k-1種取值，而i有無數(shù)種)記為i1,

10、 i2, i3使得 j1=j2=j3 = mo對這 3 個 i,同樣必然存在一對 i，不妨為(i1,i2)使(k-m,k+i1-m)且(k-m,k+i2-m)必敗或f(k-m,k+i1) 且f(k-m,k+i2)必敗。顯然與定理2矛盾，因此不存在這樣的數(shù)k。觀察這個矩陣，我們又可以得到新的定理：定理5:矩陣中每行第一個數(shù)恰巧是前面每一行中沒有出現(xiàn)過的最小正整數(shù)。證明：由定理4，矩陣中每個數(shù)字恰巧出現(xiàn)一次，而按照這個矩陣的定義，第二列的數(shù)總比同行第一列大，第一列又按照 升序排列，所以每一行的第一個數(shù)正好為前面每一行中沒有出現(xiàn)過的最小正整數(shù)。定理6:矩陣第i行的第二個數(shù)正好為第一個數(shù)加上i證明：用

11、數(shù)學歸納法。對于第一行顯然成立若對于前i - 1行均成立，則所有的(ap, ap + p) (ap為第p行第一個數(shù)，p = i,因為如果delta = i,我們來說明delta = i。首先，我們考慮從第一堆中取出p個石子，得到狀態(tài)(ai - p, ai - p + delta)，由定理5，比ai小的數(shù)都在 之前出現(xiàn)過，若ai - p出現(xiàn)在某一行的第一列，由于存在必敗態(tài)(ai - p, ai - p + d) (d delta),故(ai - p, ai - p + delta) 一定為必勝態(tài)(定理2);若ai - p出現(xiàn)在某一行的第二列，由于第一列是單增的，因而其對 應(yīng)的第一列數(shù)必小于ai

12、+ delta，故而也可推出其狀態(tài)為必勝態(tài)。對于從兩堆石子中取出相同數(shù)目的情況與之類似，容易看出一定為必勝態(tài)。于是，(ai, ai + delta)狀態(tài)的勝負性只與狀態(tài)(ai, ai + d) (d 1，所以對于不同的整數(shù)n,【na】各不相同，類似對b有相同 的結(jié)果。因此任一個整數(shù)至多在集合P或Q中出現(xiàn)一次。*現(xiàn)證明PAQ為空集；(反證法)假設(shè)k為PAQ的一個整數(shù)，則存在正整數(shù)m、n使得【ma】 二【nb】=k。即k ma、nbk+1，等價地改寫不等式為* m/(k+1) 1/a m/k及 n/(k+1) 1/b n/k,相加起來得(m + n)/(k+1) 1 (m + n)/k,即 k m

13、 + n k+1。 這與m、n為整數(shù)有矛盾，所以PAQ為空集。現(xiàn)證明Z+ = PUQ ；已知PUQ是Z+的子集，剩下來只要證明Z+ 是PUQ的子集。(反證法)假設(shè)Z+(PUQ)有一個元素k,則存在正整數(shù)m、n使得【ma】 k 【(m + 1)a】、【nb】 k 【(n + 1)b】。由此得 ma k 冬【(m + 1)a】 -1(m+1)a -1,類似地有 nb k 冬【(n+1)b】 -1(n + 1)b -1。 等價地改寫為 m/k 1/a (m+1)/(k+1)及 n/k 1/b (n+1)/(k+1)。兩式加起來，得(m + n)/k 1 (m + n+2)/(k+1)，即 m + n

14、 k k+1 0）定理二：如果（a,b）和（c,d）是2個負態(tài)，那么a,b,c,d互不相等定理三：（a,b）和（b,a）一定是完全等價的（所以本文中只出現(xiàn)（3, 5）這種狀態(tài)不出現(xiàn)（5, 3）這種狀態(tài)（除了本行）定理四：一個狀態(tài)無法轉(zhuǎn)移到任何一個負態(tài)，當且僅當它就是負態(tài)。一個狀態(tài)只要能轉(zhuǎn)移到任何一個負態(tài)，那么它就是勝態(tài)想清楚了這四點之后，可以開始找出所有負態(tài)了。（都是顯然的定理，我就不證明了）首先，（3，3）是勝態(tài)，（3，4）因為可以轉(zhuǎn)移到（1，2）所以是勝態(tài)，（3，5）因為沒法轉(zhuǎn)移到任何一個負態(tài)， 所以它就是負態(tài)。然后，（4，4）是勝態(tài)，（4，5）和（4，6）可以轉(zhuǎn)移到（3，5）所以是勝態(tài)，

15、（4，7）是負態(tài)?，F(xiàn)在，有了前3個負態(tài)，（1，2）（3，5）（4，7）光憑這3組數(shù)據(jù)是不可能發(fā)現(xiàn)規(guī)律的，但是如果結(jié)合剛剛找到它們的方法仔細思考，那就不一樣了。比如在找第4個負態(tài)的時候，我們發(fā)現(xiàn)，在（6，6）（6，7）（6，8）（6，9）.這個序列中，如果找到1個負態(tài)的話，后面的狀態(tài)都可以轉(zhuǎn)移到這個狀態(tài)，所以后面所有的狀態(tài)都是勝態(tài)。（這其 實就是定理二）可是要怎么樣知道這個序列里面有沒有一個狀態(tài)不能轉(zhuǎn)移到前面3個負態(tài)中的任何1個呢？請注意！如果這個序列中的某個狀態(tài)不能轉(zhuǎn)移到前面3個負態(tài)中的任何1個，那么它就是負態(tài)！那么關(guān)鍵來了！狀態(tài)轉(zhuǎn)移的本質(zhì)數(shù)量關(guān)系是什么？本質(zhì)數(shù)量關(guān)系就是，如果1個狀態(tài)的2個數(shù)

16、之差等于另外1個狀態(tài)的2個數(shù)之差，那么它們是可以轉(zhuǎn)移的！前面3個狀態(tài)的2個數(shù)之差分別是1，2, 3,那么很明顯，上述序列中，有且僅有1個序列是無法轉(zhuǎn)移到這3個序列的，就是那個差為4的狀態(tài)，即（6, 10）到了這里，可能你已經(jīng)明白了，如何快速求出所有的負態(tài)。負態(tài)的2個數(shù)之差的序列就是1，2，3，4.如果你認為到了這里，我只是發(fā)現(xiàn)規(guī)律，只是猜想第i個負態(tài)的2個數(shù)之差是i，請從頭再看一遍。實際上，我們不僅已經(jīng)得到了一個定理，第i個負態(tài)的2個數(shù)之差是i我們還得到了另外1個非常重要的定理，第i個負態(tài)的較小數(shù)是集合A中的最小數(shù)，其中A是自然數(shù)集，去掉前i-1個負態(tài)的2*（i-1）個數(shù)，得到的集合。結(jié)合定理

17、二可以發(fā)現(xiàn)，任何正整數(shù)都恰好出現(xiàn)在某個負態(tài)中而且僅出現(xiàn)1次！當我想到這個地方的時候，我突然想起來betty貝蒂定理其實我對這個定理印象不深，因為從來沒有用過，直到做這個題目才是第一次用。betty定理：對于任意滿足1/a+1/b=1,的正無理數(shù)a， b，都有結(jié)論：a，2a，3a，4a.b，2b，3b，4b.都是不同的數(shù)，而且覆蓋正整數(shù)集。于是我懷疑，betty貝蒂定理和本題有著本質(zhì)的聯(lián)系。因為實在是好幾年了，所以我想，還是先證明一下betty貝蒂定理，找找感覺吧。betty貝蒂定理的證明：對于任意正整數(shù)n，考慮a，2a，3a，4a.里面有多少個數(shù)小于n（如果考慮有多少個數(shù)小于等于n，那就得不到

18、什么結(jié)論，因為根本算不出來，這是由高斯函數(shù)的特性決定的）根據(jù)高斯函數(shù)的特性，kan iff kan即，kn/a （k為整數(shù)）因為n/a是無理數(shù)，所以上式還等價于k=n/a所以說，a，2a，3a，4a.里面有n/a個數(shù)小于 n同理，b，2b，3b，4b.里面有n/b個數(shù)小于 n那么，一共有多少呢？這個地方就體現(xiàn)了為什么要是無理數(shù)，因為n/a和n/b是無理數(shù)，那么就不是整數(shù)又因為 n/a+n/b=n，所以n/a+n/b=n-1所以說，對于任意正整數(shù) n，a，2a，3a，4a.b，2b，3b，4b.中有 n-1 個數(shù)小于 n由此，可以利用數(shù)學歸納法推出betty貝蒂定理。數(shù)學歸納法我就不寫了，簡述如

19、下：考慮a，2a，3a，4a.b，2b，3b，4b.中每個正整數(shù)有多少個有1個數(shù)小于2，所以有1個1有2個數(shù)小于3，所以有1個2有3個數(shù)小于4，所以有1個3 就這樣，利用第二數(shù)學歸納法，可以得到每個正整數(shù)都有且僅有1個。證畢口有了貝蒂定理，（1，2）（3, 5）（4, 7）（6，10）。這各序列的通項又要怎么求呢？還是說，這個序列根本沒法用貝蒂定理來求？我不是想死套這個定理，只是在思考，這2個東西這么像，應(yīng)該是有本質(zhì)聯(lián)系的吧？如果親愛的讀者是第一次知道貝蒂定理，可能感覺兩者的關(guān)系并不是很密切。那么你就需要像我初學貝蒂定理的時候一樣，找?guī)讉€簡單的實例，比如a=sqrt（2），或者a=sqrt（3

20、）這種簡單的例子。a=sqrt（2）時，b=sqrt（2）+2，把正整數(shù)集的劃分表示成二元組就是： （1,3）（2,6）（4,10）（5,13）（7,17）。差分別是2,4,6,8,10.規(guī)律和本題的幾乎一樣！只不過都乘了 2而已a=sqrt（3）時，b=（sqrt（3）+3）/2，把正整數(shù)集的劃分表示成二元組就是： （1,2）（3,4）（5,7）（6,9）（8,11）。差分別是1,1,2,3,3.這個貌似沒什么規(guī)律吧？為什么1個有規(guī)律，1個沒規(guī)律呢？看看a和b的值就一目了然了，a=sqrt(2)時，b=sqrt+2, kb-ka=k*2恒成立。現(xiàn)在是不是感覺這個數(shù)列和本題的數(shù)列非常像了呢？還不夠。不管是a=sqrt(2)還是a=sqrt(3)還是其實的情況，根據(jù)貝蒂定理，都可以直接推出：第i二元組中的較小數(shù)是集合A中的最小數(shù)，其中A是自然數(shù)集，去掉前i-1個二元組的2*(i-1