[算法]NIM游戏及其相应变形的分析

Iambitious

今天看到一篇不错的文章，由于有图片，所以没有转载，给个连接地址大家自己看看吧。
http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/index.html

Iambitious

忘了说一句了，文章是繁体字的，看着可能不太习惯。

soloforce

居然打不开网页

未找到服务器
Firefox  无法在 episte.math.ntu.edu.tw 找到该服务器。

Iambitious

没问题阿，我试了一下，链接有效阿。

lophyxp

将数学的网站，very good

DoDo

要是内容少的话, 哪们兄弟把内容帖一下吧, 我们教育网好可怜的

Iambitious

就像物理的不共容原理一樣，數學遊戲的趣味性和其數學理論的完整性，成為互相排斥的兩部份。一種遊戲完全被數學決定以後，玩的人只要曉得其中的理論，無不處於優勢。遊戲本身則成為數學的計算，玩起來必索然無味；但如果將它視為數學問題處理，則蘊藏有甚多美妙的理論在其中。富有挑戰性的遊戲，則沒有固定的規律可尋，必須隨機應變，靠臨場的機智和以往的經驗取勝，玩者有味；但在數學理論上則沒有什麼可言。

拈及其各種變型遊戲大都屬於前者。當做一種學問，我們只關心其富有趣味的數學理論。

在所有雙人對局遊戲中，拈是極其古老且饒富興趣的一個課題。據說，拈源自中國，經由被販賣到美洲的奴工們外傳。辛苦的工人們，在工作閒暇之餘，用石頭玩遊戲以排遣寂寞。流傳到高級人士，則用辨士 (Pennils)，在酒吧櫃檯上玩。最有名的是將十二枚辨士分三列排成「三、四、五」的遊戲，如下圖：

遊戲的規則很簡單。兩人輪流取銅板，每人每次需在某一列取一枚或一枚以上的銅板，但不能同時在兩列取銅板，直到最後，將銅板拿光的人贏得此遊戲。也可以做相反的規定：最後將銅板拿光的人輸。

一個頭腦靈活的賭棍不久就會發現，先取的人，在第一列的三枚銅板中取走二枚，就能穩操勝算。一個顯而易見的規律是，只要你留下兩列枚數相同的銅板，必可獲勝。在這裏對稱扮演極重要的角色。

如果這個遊戲只是「三、四、五」型態，那麼不久後，大部份人就能熟悉其中規律，並且變得沒有興趣。有一個改變的方法是，將銅板的列數增加，每一列的枚數改變。這樣的做法，的確使人有毫無規律的感覺，至少不至於像「三、四、五」型態的拈一樣易於把握。

直到本世紀初，哈佛大學數學系副教授查理士．理昂納德．包頓 (Chales Leonard Bouton) 提出一篇極詳盡的分析和證明，利用數的二進位表示法，解答了這個遊戲的一般法則：對任意列數的銅板，每列有任意枚數，如何取得致勝之道？

在包頓的術語中，拿過後剩下的殘局不是安全 (safe) 就是不安全 (unsafe) 的局面。在所有安全的情況下，不管對方如何拿總是到一不安全的情況，你可以再取適當枚數的銅板（在適當的某一列），達到另一安全的情況，這樣一直到拿光銅板為止，當然最後一次拿光銅板的一定是你。反之，你如果留下不安全的情況，對方必有方法在適當的某一列，取走適當枚數的銅板，達到他的安全情況，也就是說你輸定了。

包頓的方法很簡單。首先，將各列銅板的枚數化成二進位數，相加，但不進位，然後再看和的各個位數。如果和的各個位數都是偶數，則表示一安全殘局;否則，如果有一位是奇數，則為不安全殘局。例如「三、四、五」遊戲，一開始就是不安全殘局，先拿的人可以適當取二枚而造成他的安全殘局。
[例一]

另一個不安全殘局的例子如下：
[例二]


或者

為什麼安全殘局和不安全殘局可以利用上述的方法判定呢？這個道理其實很簡單。首先，如果將各列銅板數化為二進位表示法，相加，但不進位，得到的各個位數都是偶數的話，不論對方取那一列，多少枚銅板，則那一列銅板數所對應的二進位表示法中，必有某一位或數位由 0 變成 1 或者由 1 變成 0，其相加的和也相對的有某一位或數位由偶數變成奇數。例如，{1,4,5}這個安全殘局，從第二列的 4 枚銅板取走 2 枚，則


相反的，如果和的某一位或數位是奇數，則我們有辦法在某一列取走適當枚數的銅板，使得新的和的各個位數都是偶數。首先，選取和中所有為奇數的各個位數；例如在 {14,15,18,22} 的例子中和的第 1 和第 3 位是奇數。其次看這些位數中那一個是最左邊一位；本例中當然是第 3 位。找某一列，使其二進位表示法在此位上剛好是 1；本例中，可以找第一例的14，也可以找第二列的15。然後將此列的銅板數所對應的二進位數中，凡是第 ai 位，都改變其數值，亦即若為 0 則變為 1，若為 1 則變為 0，如此得到一新數，我們只要在此列銅板取走適當的數目，使達到這新的枚數，即可以使新的和的各個位數都是偶數；例如，若考慮第一列的 14=1110 枚銅板，將其第 1 和第 3 位改變得到 1011=11 枚銅板，所以要在第一列取走 3 枚銅板。

相反規定，拿光銅板的人算輸峙，只耍將上面的規律略加修飾，也可以控制局面。如果你一直擁有安全殘局，對方一直處於不安全的情況，到某一時候，對方留下來的不安全殘局一定會出現一種特殊型態，即是，除某一列銅板的枚數大於 1，其他各列均只有一枚銅板（拿光的各列不管它），這時候你的拿法要開始注意，你需將較多枚銅板這一列全部取光，或者拿到只剩下一枚，決定採取何者，完全看你拿了之後，要能使剩下的列數為奇數，當然每一列均只有一枚銅板。顯而易見的是，以後一人都取一列，也是一枚，到最後拿的一定是對方，於是你就贏了。

有很多人把這個方法寫成電腦程式，來和人對抗，不知就理的人被騙得團團轉，無不驚嘆電腦的神奇偉大。其實說穿了，只因為它計算比人快，數的轉化為二進位其速度快得非人能比，如此罷了。

Iambitious

用來玩拈的道具不限於銅板。工餘之時，石頭可以玩；無聊磕瓜子時，瓜子可以玩；圍棋子可以玩……。也可以將石頭分堆放置，一堆相當於一列。這些都不是重點，我們甚至可以改變取銅板的規定，最後取光時輸贏的規定……，於是，各種不同的變型遊戲遂產生。

在拈的遊戲中，如果只有兩列銅板，則很容易看出來，留下兩列枚數相同的銅板是致勝的安全殘局。也就是我們一開始說的對稱這個想法。事實上，包頓很巧妙的將對稱化成二進位和的各個位數為偶數，將問題給一般化，這是很天才的想法。所以兩列的拈是沒有什麼可說的。

將拈的規定略加修改，成為只有兩列的威氏遊戲，卻極其有意思。規定是這樣的，銅板只有兩列，每列的枚數隨玩者任意規定，兩人輪流取銅板，取的時候，需要任一列中取一枚或多枚銅板，或者同時在兩列取同樣枚數的銅板，直到最後將銅板取光的人贏。當然也可以像拈一樣有相反的規定，最後將銅板取光的人輸。今只討論前者。

拈的玩法完全不能適用於威氏遊戲。所有拈的安全殘局 {n,n}，在威氏遊戲中都是不安全殘局。因為我們加了一個規定，可以從兩列銅板中同時取相同枚數的銅板。

    [例3] 若 n 是正整數，則 {0,n} 和 {n,n} 都是不安全殘局。

    [例4] {1,2} 是安全殘局。因為

    不管如何取，總是成為不安全殘局。

    [例5] {3,5} 是安全殘局。因為

    不管對方如何取，不是到達例 3 的不安全殘局，就是你可以再適當取，使成例 4 的安全殘局。

繼續推演下去，可以得到許多組安全殘局 {1,2},{3,5},{4,7},{6,10},…。一般而言，第 n 組安全殘局 {an,bn} 可由下式定義得到

    (1) a1=1,b1=2。
    (2) 若 已經求得，則定義 an 為未出現在以上這 2n-2 個數中的最小整數。
    (3) bn=an+n。

做成表就是
n         1         2         3         4         5         6         7         8         9         10
an         1         3         4         6         8         9         11         12         14         16
bn         2         5         7         10         13         15         18         20         23         26
由(1)、(2)、(3)所定義的二數列 [img]http://episte.math.ntu.edu.tw/articles/mm/mm_03_2_02/img11.gif[/img 和 ，具有下列特性：
    (甲) 數列 和 均是嚴格遞增數列，而且 bn=an+n。
    (乙) , 其中 N 表示正整數的集合， ,
    (丙) 若 {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，且 時，y-x<m，令 k=y-x，則 y-bk=x+k-(ak+k)=x-ak>0。在 x 中取x-ak，在 y 中取 y-bk=x-ak 則變成 {ak,bk}。

這個定理不但告訴我們 {an,bn} 是威氏遊戲的安全殘局，其證明過程更暗含從不安全殘局取銅板變成安全殘局的法則。我們只要記住這個法則，還有 {an,bn} 組合，則無不處於優勢。但是有一個問題是，當數目很大的時候，要記住一大堆 {an,bn} 是一件非常吃力不討好的工作。我們於是自然會問，有沒有像拈類似的法則用來判斷任何一組 {x,y} 是否為威氏遊戲的安全殘局，而不必逐一計算 {a1,b1},{a2,b2} …。答案是有的，在解答這之前，我們需要談談費氏數列及相關的問題。

Iambitious

there are still 4 sections left, to be continued...

soloforce

很有意思！
辛苦Iambitious了！