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

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

3、來表示狀態，并畫在平面直角坐標系上。 用之前的定理：有限個結點的無回路有向圖有唯一的核中所述的方法尋找必敗態。先標出(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的必敗態的話，前面的一些是(0,0),(1,2),(3,5),(4,7),(6,10),.接下來就是找規律的過程了，可能很辛苦，但是我寫得也不容

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

5、前的必敗態中出現過，一旦把左邊堆拿少了，我們只要再拿 成那個數相應的必敗態即可。情況二(從右邊堆拿走不太多)：這使得兩堆之間的差變小了，比如拿成了(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)出發走向的狀態都可以走回核中.故原命題成立.以上兩個命題對于確定(an,bn)是完備的了，給定(

6、0,0)然后按照這兩個命題，就可以寫出(1,2),(3,5),(4,7),.這樣我們得到了這個數列的遞推式，以下我們把這兩個命題當成是(3間血)的定義。先證明兩個性質：性質一：核中的an,bn遍歷所有正整數。分析:由命題一，二可得an,bn是遞增的，且由an的定義顯然。性質二：A=an:n=123,.,B=bn:n = 1,23.，則集合 A,B 不交。分析：由核是內固集，顯然?？吹竭@里大家有沒有想到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、到此，我們找到了該必敗態的通項公式。實際上這組Beatty序列還有一些別的性質，比如當一個數是Fibonacc i數的時候，另一個數也是Fibonacc i數； 而且兩者的比值也越來越接近黃金比，這些性質在得到通項公式之后不難證明?？偟膩碚f，這個問題給我們了哪些啟示呢？首先用定理所說的方法找核，然后給出核的規律(遞推，或是通項)并 且證明。方法二定理0:一個狀態是必敗態，當且僅當它的所有后繼狀態都是必勝態；而一個狀態是必勝態，只要它的后繼狀態有 一個以上的必敗態即可。證明略去。容易發現下面的定理：定理1 ：(a,b)和(b, a)的勝負性是相同的(a b)。證明：如果(a, b)是必勝態，那么

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

9、狀態中較小的數字放在前面，每行寫一個狀態，去掉括號并按照升序排列每行的第一個數，就構成了如下 的矩陣：1 2576 10假設數字1在矩陣中出現兩次或兩次以上，則有(k,a), (k,b)都為必敗態，與定理2矛盾。假設數字10)，則對任意i,必然存在j(0jk)使得 (k-j,k+i-j)或(k,k+i-j)或(k-j,k+i)為必敗態(若不如此，則無論如何取石子，對方必勝)，根據假設，顯然(k,k+i-j)必 勝，因此，對任意 i,必有(k-j,k+i-j)或(k-j,k+i)=0, (0jk)必敗根據鴿巢原理，必然存在3個i的取值(其實是無窮多個，j只有k-1種取值，而i有無數種)記為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矛盾，因此不存在這樣的數k。觀察這個矩陣，我們又可以得到新的定理：定理5:矩陣中每行第一個數恰巧是前面每一行中沒有出現過的最小正整數。證明：由定理4，矩陣中每個數字恰巧出現一次，而按照這個矩陣的定義，第二列的數總比同行第一列大，第一列又按照 升序排列，所以每一行的第一個數正好為前面每一行中沒有出現過的最小正整數。定理6:矩陣第i行的第二個數正好為第一個數加上i證明：用

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

12、+ delta，故而也可推出其狀態為必勝態。對于從兩堆石子中取出相同數目的情況與之類似，容易看出一定為必勝態。于是，(ai, ai + delta)狀態的勝負性只與狀態(ai, ai + d) (d 1，所以對于不同的整數n,【na】各不相同，類似對b有相同 的結果。因此任一個整數至多在集合P或Q中出現一次。*現證明PAQ為空集；(反證法)假設k為PAQ的一個整數，則存在正整數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為整數有矛盾，所以PAQ為空集?，F證明Z+ = PUQ ；已知PUQ是Z+的子集，剩下來只要證明Z+ 是PUQ的子集。(反證法)假設Z+(PUQ)有一個元素k,則存在正整數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個負態，那么a,b,c,d互不相等定理三：（a,b）和（b,a）一定是完全等價的（所以本文中只出現（3, 5）這種狀態不出現（5, 3）這種狀態（除了本行）定理四：一個狀態無法轉移到任何一個負態，當且僅當它就是負態。一個狀態只要能轉移到任何一個負態，那么它就是勝態想清楚了這四點之后，可以開始找出所有負態了。（都是顯然的定理，我就不證明了）首先，（3，3）是勝態，（3，4）因為可以轉移到（1，2）所以是勝態，（3，5）因為沒法轉移到任何一個負態， 所以它就是負態。然后，（4，4）是勝態，（4，5）和（4，6）可以轉移到（3，5）所以是勝態，

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

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

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

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

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

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