上頁　1│2│3│4│5│6　次頁

拈及其各種變形遊戲 （第 4 頁）

張鎮華

 

首頁 | 搜尋

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

•註釋
•對外搜尋關鍵字
 
(四)威氏遊戲的致勝方法

現在回到第(二)節的數列 {an} 和 {bn}。一個相當有趣的事實是，如果將威氏遊戲的各組安全殘局 {an,bn} 用費氏數列標準表示法表示出來，如下表：

\begin{displaymath} \begin{array}{cccccccccccc} n&&&a_n&&&&&b_n&&&\\ 1&&&&&1&&&... ... 7&1&0&1&0&0&1&0&1&0&0&0\\ 8&1&0&1&0&1&1&0&1&0&1&0 \end{array}\end{displaymath}

仔細觀察，各個 bn 恰好是 an 後面加一個 0，每個 an 最右邊有偶數個連續的 0（包括沒有 0），當然 bn 最右邊有奇數個連續的 0。有了這個結果，我們要檢查一組 {x,y}（其中 $x\leq y$）是否安全殘局，就可以將 x 和 y 表成費氏數列標準表示法，再看看是否合於上述的條件即可。 這中間的優點是，我們不必再計算所有 $a_n\leq x$ 的安全殘局 {an,bn}，以決定 {x,y} 是否安全。更重要的是，我們將有一種簡便的方法，可以將不安全殘局 {x,y} 適當的取成某一安全殘局 {an,bn}。

當然，數論上的一些結果告訴我們 $a_n=[n\cdot\frac{\sqrt{5}-1}{2}]$, $b_n=[n\cdot\frac{\sqrt{5}+1}{2}]$,（[x] 表示小於或等於 x 的最大整數，例如 [2.99]=[2.0]=[2]=2）由定理1，我們幾乎要求出 2x/(sqrt5-1) 組 {an,bn} 才能順利的判定安全殘局，以及由不安全殘局拿成安全殘局的方法。當 x 大的時候，這麼多的資料處理起來必然不方便。

上述 {an,bn} 的性質，只是依觀察而得，現在我們要證明其真實性。我們所以要這樣做，不光是因為數學上的嚴密性，在證明的過程中，用到的一些計算，將很有用處。

首先將自然數分成 A 和 B 兩部份，A 是所有費氏標準表示法中右邊有偶數個連續 0 的自然數的集合，B 則是所有費氏漂準表示法中右邊有奇數個連續 0 的自然數的集合。將 A 中之數由小而大排成一數列 $\{a_n'\}_{n=1}^{\infty}$ 設 bn' 是 an' 費氏標準表示法右邊再加一個 0 者。我們將證明

\begin{displaymath} A=\{a_n'\vert n\mbox{{\fontfamily{cwM2}\fontseries{m}\select... ...s0.1pt{\fontfamily{cwM1}\fontseries{m}\selectfont \char 98}}\} \end{displaymath}

且合於第(二)節的(甲)(乙)條件。所以，事實上就是

\begin{displaymath} \{a_n\}_{n=1}^{\infty}\quad\mbox{\hskip 1.2pt plus0.4pt minu... ...ontseries{m}\selectfont \char 184}}\quad\{b_n\}_{n=1}^{\infty} \end{displaymath}

因此證明了上述的性質。(乙)易於知道成立。因為 $\{a_n'\}_{n=1}^{\infty}$ 和 $\{b_n'\}_{n=1}^{\infty}$ 都是嚴格增加數列，為了證明(甲)，我們只要證明 bn'=an'+n 就可以，茲分下面兩步驟，證明之。

(第一) bn'-an'，隨 n 增加而增加。也就是，當 n>m 時， bn'-an'>bm'-am'。

[證] 假設

\begin{displaymath} \begin{array}{lll} a_n'&=&l_rf_r+l_{r-1}f_{r-1}+\cdots+l_0f_... ...r+1}+\overline{l}_{r-1}f_r+\cdots+\overline{l}_0f_1 \end{array}\end{displaymath}

上面均是標準表示法，但左邊有的填 0（即 lr 或 $\overline{l}_r$ 可能為 $0\cdots$ 等）以便對齊。 n>m 表示 an'>am'，也就是有一個 s<r 使得 $l_i=\overline{l}_i$ 對每一個 i>s 成立， $l_s>\overline{l}_s$。因為

\begin{eqnarray*} b_n'-a_n'&=&l_rf_r+l_{r-1}f_{r-1}+\cdots+l_1f_1+l_0\\ b_m'-a_... ...overline{l}_{r-1}f_{r-1}+\cdots+\overline{l}_1f_1+\overline{l}_0 \end{eqnarray*}


可見

bn'-an'>bm'-am'

(第二) 對於任一自然數 x，有一組 {an',bn'} 使得 bn'=an'+x。

[證]當 x 的費氏標準表示法右邊有奇數個連續的 0 時，取 an'=x0(f), bn'=x00(f) 即可以。

當 x 的費氏標準表示法右邊有偶數個連續的 0 時，即

\begin{displaymath} x=l_rf_r+l_{r-1}f_{r-1}+\cdots+l_{2m}f_{2m},l_{2m}=1 \end{displaymath}

取

\begin{eqnarray*} a_n'&=&l_rf_{r+1}+l_{r-1}f_r+\cdots+l_{2m+1}f_{2m+2}+f_{2m}+f_... ...r-1}f_{r+1}+\cdots+l_{2m+1}f_{2m+3}+f_{2m+1}+f_{2m-1}+\cdots+f_1 \end{eqnarray*}


利用

\begin{eqnarray*} &&(f_{2m+1}+f_{2m-1}+\cdots+f_1)-(f_{2m}+f_{2m-2}+\cdots+f_0)\\ &=&(f_{2m+2}-1)-(f_{2m}-1)=f_{2m+2}-f_{2m+1}=f_{2m} \end{eqnarray*}


可見 bn'=an'+x 成立。

(第一)和(第二)證明了bn'=an'+n的確成立。

上面的證明不但說明了 {an,bn} 具有所述的性質，即是 an 為第 n 個費氏標準表示法之最右邊有偶數個連續 0 的自然數，bn 是第 n 個費氏標準表示法之最右邊有奇數個連續 0 的自然數，尤有進者，bn 的表示法等於 an 表示法右邊再加一個 0 而已。

而且由(第二)可以知道，對於任何一個自然數 x，不必用歸納法從 a1,b1,a2,b2,… 算起，一直求至 ax,bx。 直接就可以算出 ax 和 bx 來。所以在利用定理1 的時候，我們就可以不必記憶一大堆 {an,bn} 值了。

   

上頁　1│2│3│4│5│6　次頁

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

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


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