已在第一頁 123456 次頁

 


首頁 | 搜尋

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

註釋
 

拈及其各種變形遊戲

張鎮華

 
 


(一)拈 (Nim) 這種遊戲

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

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

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

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

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

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

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

直到本世紀初,哈佛大學數學系副教授查理士.理昂納德.包頓 (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。然後將此列的銅板數所對應的二進位數中,凡是第 ai 位,都改變其數值, 亦即若為 0 則變為 1,若為 1 則變為 0,如此得到一新數,我們只要在此列銅板取走適當的數目,使達到這新的枚數,即可以使新的和的各個位數都是偶數; 例如,若考慮第一列的 14=1110 枚銅板,將其第 1 和第 3 位改變得到 1011=11 枚銅板,所以要在第一列取走 3 枚銅板。

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

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

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

已在第一頁 123456 次頁

回頁首
 
(若有指正、疑問……,可以在此 留言寫信 給我們。)
EpisteMath

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


編輯:李渭天 最後修改日期:4/26/2002