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

　1│2│3│4│5│6　

拈及其各種變形遊戲（第 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+1 或 k+2 的倍數有關係。

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

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

這個遊戲和第一個單堆遊戲有點類似，卻不相同。如果骰子出現i的時候，輪到你，則從1到6中的各數有兩個，即是i和7-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}$

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

(i) 如果 $n\geq 1$ ，則 f_n<f_n+1<2f_n。

[證明]因為 f₁=2，f₂=3，f₃=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=f_k₁+f_k₂+ … +f_{k_n-1}+f_{k_n} 個石頭，其中 $k_i\geq 2+k_{i+1}$ , i=1,2,…,n-1，而且對方下次所能取走的石頭數目小於 f_{k_n} 則你留下的是一安全殘局。

[證明] 假設對方拿走 $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'=f_k₁+f_k₂+ … +f_{k_n-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}$

也就是對方下次所能取走的石頭數目小於 f_{k_n+1} 如此又可用歸納法繼續推演本定理。其次，如果 k_n>2+k_n+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$ 為奇數，而且 k_n-t=k_n+1 或 1+k_n+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'<2f_{k_n-t}<f_{k_n-t}+f_{k_n-t+1}=f_{k_n-t+2}

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

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

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

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

$\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}$

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

　1│2│3│4│5│6　


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

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

編輯：李渭天

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