拈及其各種變形遊戲

　1│2│3│4│5│6　

首頁 | 搜尋

．原載於數學傳播第三卷第二期
．作者當時就讀於美國康乃爾大學

‧註釋

拈及其各種變形遊戲

張鎮華

(一)拈 (Nim) 這種遊戲
(二)威氏遊戲 (Wythoff's Game)
(三)費氏數列及進位法
(四)威氏遊戲的致勝方法
(五)單堆遊戲
(六)結語

(一)拈 (Nim) 這種遊戲

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

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

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

$\begin{displaymath} \begin{array}{cccccc} \mbox{{\fontfamily{cwM2}\fontseries{m}... ... 127}}&\bigcirc&\bigcirc&\bigcirc&\bigcirc&\bigcirc \end{array}\end{displaymath}$

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

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

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

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

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

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

[例一]

$\begin{displaymath} \begin{array}{rcccc} 3&=&&1&1\\ 4&=&1&0&0\\ +)5&=&1&0&1\\ ... ...amily{cwM1}\fontseries{m}\selectfont \char 1})}&&&& \end{array}\end{displaymath}$

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

[例二]

$\begin{displaymath} \begin{array}{rcccccc} 14&=&&1&1&1&0\\ 15&=&&1&1&1&1\\ 18&... ...ily{cwM1}\fontseries{m}\selectfont \char 1})}&&&&&& \end{array}\end{displaymath}$

$\begin{displaymath} \stackrel{\mbox{{\fontfamily{cwM2}\fontseries{m}\selectfont ... ...ily{cwM1}\fontseries{m}\selectfont \char 1})}&&&&&& \end{array}\end{displaymath}$

或者

$\begin{displaymath} \stackrel{\mbox{{\fontfamily{cwM2}\fontseries{m}\selectfont ... ...ily{cwM1}\fontseries{m}\selectfont \char 1})}&&&&&& \end{array}\end{displaymath}$

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

$\begin{displaymath} \begin{array}{ccl} \mbox{{\fontfamily{cwM0}\fontseries{m}\se... ...ntfamily{cwM0}\fontseries{m}\selectfont \char 229}} \end{array}\end{displaymath}$

$\begin{displaymath} \begin{array}{rcccc} \mbox{{\fontfamily{cwM0}\fontseries{m}\... ...wM0}\fontseries{m}\selectfont \char 184}}&&2&0&2\\ \end{array}\end{displaymath}$

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

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

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

對外搜尋關鍵字：
．費氏數列
．進位法

　1│2│3│4│5│6　


	（若有指正、疑問……，可以在此留言或寫信給我們。）

EpisteMath (c) 2000 中央研究院數學所、台大數學系
各網頁文章內容之著作權為原著作人所有

編輯：李渭天

最後修改日期：4/26/2002