上頁 123456 次頁

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

張鎮華

 

首頁 | 搜尋

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

註釋
對外搜尋關鍵字
 
(五)單堆遊戲

在所有拈的變型遊戲中,單堆遊戲似乎是比較簡單的。最常見而為大眾熟悉的玩法是這樣的:「兩人輪流取一堆石頭,每人每次最少取 1 個,最多取 k 個,最後取光石頭的人贏得此遊戲。」請問有何致勝之道?

和前面一樣,所有的情況,可以分為安全和不安全兩種。在這 k+1 這個數扮演著極重要的角色,因為每次某一人拿的石頭數 i,合於 $1\leq i<k+1$,可見 $1\leq k+1-i\leq k$,另一人總是可以取 k+1-i 個石頭,使這兩次所取的石頭共有 k+1 個,由是可見 k+1 是安全殘局,利用歸納法則 k+1 的倍數必為安全殘局。 反之,不是 k+1 倍數的任一自然數 n=q(k+1)+r,其中 $1\leq r\leq k$,一次拿 r 個石頭就能到達 q(k+1),即某一安全殘局,可見此時為不安全殘局。

相反的規定:「最後取光石頭的人輸」,也可以分析知道,安全殘局是 q(k+1)+1 這種型態的數。

並不是所有單堆遊戲都是如此容易的,例如「奇偶遊戲」則是較複雜的一種。所謂「奇偶遊戲」只是將上述的問題略加修改,最後取光石頭時的輸贏的規定不同,即「兩人輪流取一堆石頭,每人每次最少取 1 個,最多取 k 個,到最後石頭被取光時,若手中所有石頭總數為奇數,則此人贏得此遊戲。(也可以規定石頭總數為偶數的人贏得此遊戲)。」顯而易見的是,原先這堆石頭的總數要是奇數才有意義。 這個遊戲較前者更複雜,其安全殘局視k的奇偶和 k+1k+2 的倍數有關係。

另一個和骰子有關的單堆遊戲由古先生 1 提出來,問題是這樣的:「有一堆石頭,數目不拘。首先任意擲一骰子,看出現幾點,就取去幾個石頭。然後兩人輪流翻轉骰子到前次骰子出現那一面的旁邊四面中任一面,但不可以翻到對面,也不可以不翻,翻到幾點,就取去幾個石頭,如此輪流玩到一方沒有辦法拿石頭,也就是說,剩下的石頭數比他翻到的數目還小的時候,則他就算輸了。」

首先耍瞭解的一點是,骰子上面六個數目安排的方法。從1到6的各個自然數在骰子上各出現一次, 1的對面是6,2的對面是5,3的對面是4。

這個遊戲和第一個單堆遊戲有點類似,卻不相同。如果骰子出現i的時候,輪到你,則從1到6中的各數有兩個, 即是i7-i,你不能翻到,其餘四個隨你高興愛翻那一個都可以。所以每次你能夠取的石頭數,依前次對方所翻到的數目而定,而對方翻的數又因你前次翻的而定,如此相互影響,就顯得很複雜了。 仔細分析的結果,可以發現其安全殘局和8的倍數有密切關係。有興趣的讀者可以自已試試看。

如果把骰子加成兩個,然後規定每次翻兩個骰子,把翻到的兩個數字和算出來,取掉同樣數目的石頭, 則又如何呢?如果還是有兩個骰子,但每次只任選其中一個將它翻到新數目,看這數目是多少,就取掉多少石頭,則又如何? 或者,還是兩個骰子,每次只任意翻轉其中一個到新數目,但把這個新數目和另一個未翻的骰子相加,算出其和,取掉同樣數目的石頭,則又如何? 當然,增加骰子的數目,則遊戲更複雜。

最後我們想仔細討論的一個單堆遊戲叫做「雙倍遊戲」。這個遊戲和骰子的單堆遊戲有一共同的特性:每次所拿石頭的個數受上次對方所拿石頭的個數影響。

問題是這樣的:「兩人輪流取石,每人每次至少取 1 個石頭,至多取上次對方所拿石頭數目的兩倍;最後拿光石頭的人贏得此遊戲。當然,第一個人不能第一次就取光所有石頭。」

[例8] 2 是安全殘局,因對方只能取 1。

[例9] 3 是安全殘局。因

\begin{displaymath}
3\stackrel{\mbox{\hskip 1.2pt plus0.4pt minus0.2pt{\fontfami...
...har 166}\hskip 1.2pt plus0.4pt minus0.2pt1}}{\longrightarrow}0
\end{displaymath}

[例10] 5 是安全殘局。因

\begin{displaymath}
\begin{array}{cc}
5\stackrel{\mbox{\hskip 1.2pt plus0.4pt mi...
...ntfamily{cwM1}\fontseries{m}\selectfont \char 1})}&
\end{array}\end{displaymath}

如此繼續推演下去,一個很有意思的結論是,所有費氏級數的項 fn 均是安全殘局其餘都是不安全殘局。要證明這件事情可以分幾步完成,主要的概念還是在於自然數的費氏數列標準表示法。

(i) 如果 $n\geq 1$,則 fn<fn+1<2fn
[證明]因為 f1=2f2=3f3=5,所以 n=1,2, 時易知為對。

n<k 時定理成立,則

\begin{displaymath}
\begin{array}{l}
f_{k-2}<f_{k-1}<2\cdot f_{k-2}\\
f_{k-1}<f_k<2\cdot f_{k-1}
\end{array}\end{displaymath}

兩式相加

\begin{displaymath}
f_k<f_{k+1}<2\cdot f_k
\end{displaymath}

由歸納法得證。

(ii) 如果你留下 x=fk1+fk2++fkn-1+fkn 個石頭,其中 $k_i\geq 2+k_{i+1}$, i=1,2,…,n-1,而且對方下次所能取走的石頭數目小於 fkn 則你留下的是一安全殘局。

[證明] 假設對方拿走 $y=f_{k_{n+1}}+f_{k_{n+2}}+\cdots+f_{k_{n+m}}$ 個石頭,其中 $k_n\geq 1+k_{n+1}$, $k_{n+i}\geq 2+k_{n+i+1}$, i=1,2,…,m-1

$k_n\leq 2+k_{n+1}$ 時, $y\geq f_{k_{n+1}}\geq f_{k_{n-2}}$

\begin{displaymath}
y'=f_{k_n}-y\leq f_{k_n}-f_{k_{n-2}}=f_{k_{n-1}}<2f_{k_n-2}\leq 2y
\end{displaymath}

所以你可以取走 y' 個石頭,使剩下 x'=fk1+fk2++fkn-1 個石頭,而且

\begin{displaymath}
2y'=2(f_{k_n}-y)<2f_{k_n}<f_{k_n}+f_{k_{n+1}}=f_{k_{n+2}}\leq f_{k_{n-1}}
\end{displaymath}

也就是對方下次所能取走的石頭數目小於 fkn+1 如此又可用歸納法繼續推演本定理。 其次,如果 kn>2+kn+1 分解

\begin{displaymath}
f_{k_n}=f_{k_{n-1}}+f_{k_{n-2}}+f_{k_{n-5}}+\cdots
+ f_{k_n-t-2}+f_{k_n-t}+f_{k_n-t-1}
\end{displaymath}

其中 t$\geq 3$ 為奇數,而且 kn-t=kn+11+kn+1

\begin{displaymath}
y'=f_{k_n-t}+f_{k_n-t-1}-y<f_{k_n-t}\leq f_{1+k_{n+1}}<2f_{k_{n+1}}\leq 2y
\end{displaymath}

所以你可以取走 y' 個石頭,使剩下

\begin{displaymath}
x'=f_{k_1}+f_{k_2}+\cdots+f_{k_{n-1}}+f_{k_{n-1}}+f_{k_{n-3}}
+ \cdots + f_{k_n-t+2}
\end{displaymath}

個石頭,而且

2y'<2fkn-t<fkn-t+fkn-t+1=fkn-t+2

也就是下次對方所能取走的石頭數目小於 fkn-t+2。同理可用歸納法。

(iii) 雙倍遊戲中的安全殘局是 fn, n=1,2,…。

[證明] x=fn 時就如(ii)所述,對方所取的石頭不超過 $\delta_n$,所以你是留下安全殘局。

若一開始 x 不是 fn 型態,化為費氏標準式,

\begin{displaymath}
x = f_{k_1}+f_{k_2}+\cdots,
\mbox{{\fontfamily{cwM0}\fontse...
...eries{m}\selectfont \char 50}}k_i\geq 2+k_{i+1},i=1,\cdots,m-1
\end{displaymath}

對方可以取去 fkm 剩下 $x'=f_{k_1}+\cdots+f_{k_{m-1}}$;輪到你時不得取超過 $2f_{k_m}<f_{k_{m+2}}\leq f_{k_{m+1}}$, 由(ii)可知他留下了他的安全殘局,所以一開始是你的不安全殘局。

   

上頁 123456 次頁

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

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


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