上頁 123456 次頁

拈及其各種變形遊戲 (第 2 頁)

張鎮華

 

首頁 | 搜尋

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

註釋
對外搜尋關鍵字
 
(二)威氏遊戲 (Wythoff's Game)

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

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

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

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

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

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


\begin{picture}(200,100)(0,0)
\put(20,70){\makebox(0,0)[r]{$\{1,2\} \; $}}
\put(...
...ntseries{m}\selectfont \char 40}}$}}
\put(20,10){\vector(1,0){70}}
\end{picture}

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

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


\begin{picture}(230,230)(0,0)
%% row 11
\put(15,210){\makebox(0,0){ $\{3,5\}$\ }...
...ntseries{m}\selectfont \char 40}}$}}
\put(30,10){\vector(1,0){70}}
\end{picture}

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

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

(1) a1=1,b1=2
(2) 若 $a_1,b_1,\cdots,a_{n-1},b_{n-1}$ 已經求得,則定義 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)所定義的二數列 $\{a_n\}_{n=1}^{\infty}$$\{b_n\}_{n=1}^{\infty}$,具有下列特性:

(甲) 數列 $\{a_n\}_{n=1}^{\infty}$$\{b_n\}_{n=1}^{\infty}$ 均是嚴格遞增數列,而且 bn=an+n
(乙) $A\bigcup B=\mathbf{N}$, $A\bigcap B=\emptyset$ 其中 N 表示正整數的集合, $A=\{ a_n\vert n \in \mathbf{N} \}$, $B=\{ b_n\vert n \in \mathbf{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} 中的 anxbny 而能達到另一組 {am,bm},則 an-x=ambn-y=bm

(i) 當 x=0y>0 時,an=amn=m,得 y=0,矛盾。
(ii) 當 x>0y=0 時,bn=bmn=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\geq 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,且 $a_m=x\leq y<b_m=a_m+m$ 時,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} …。答案是有的,在解答這之前,我們需要談談費氏數列及相關的問題。

   

上頁 123456 次頁

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

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


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