費波納契的遊戲(the game of Fibonacci)

費波納契的遊戲(the game of Fibonacci)
國立台灣師範大學數學系許志農教授/國立台灣師範大學數學系許志農教授責任編輯

摘要:本文將介紹一道與費波納契數列有關的遊戲。

費波納契數列 \(<f_n>\) 是滿足 \(f_1=1,f_2=1\) 及遞迴關係

\(f_n=f_{n-1}+f_{n-2}~~~(n\ge 3)\)

的數列（後項等於前兩項之和），其前幾項可以算得為

\(f_3=2,~f_4=3,~f_5=5,~f_6=8,~f_7=13,~f_8=21,\cdots\)

在 1202 年，義大利數學家費波納契出版了他的「算盤書」，他在書中提出了一道兔子繁殖的問題：有一對兔子每月能生一對小兔（一雄一雌），而每對小兔在牠出生後的第三個月，又能開始生一對小兔。在不發生死亡的情況下，由一對兔子開始，一年後會有多少對兔子？

關於這問題：在第一個月時，只有一對小兔子，過了一個月，那對兔子成熟了，在第三個月時便生下一對小兔子，這時有兩對兔子。再過多一個月，成熟的兔子再生一對小兔子，而另一對小兔子長大，有三對小兔子。如此推算下去，我們便發現了費波納契數列的規律，也就是說，第 \(n\) 個月應該有 \(f_n\) 對兔子才是。

費波納契數列雖然起源於兔子問題，但是這數列幾乎與我們的生活息息相關，例如，人體美學的黃金比例，生物世界的規律，股票市場的波浪理論…等都與費波納契數列有很大的關連。

費波納契數列有一個有趣的現象：

「每一個正整數都可以寫成若干個不相鄰的費波納契數之和，而且這種寫法是唯一的。」

例如 \(15=2+13,~17=1+3+13,~30=1+8+21\cdots\) 等，這個奇妙的現象稱為齊肯多夫定理。

齊肯多夫定理有點像「每一個正整數都可以唯一的寫成若干個質數的乘積」現象（算術基本定理）一樣，差別在於：齊肯多夫定理在談加法，使用的數列是費波納契數列；而算術基本定理在談乘法，使用的數列是質數數列。

現在讓我們來欣賞這節所要介紹的遊戲：

有 \(N~(N> 1)\) 顆石頭，甲、乙兩人輪流照以下規則取石頭：

1. 每次至少取一顆或一顆以上的石頭。
2. 先取的甲在第一輪時，不能將所有的石頭取完（至少留下一顆石頭）。
3. 每次取的石頭數目不得超過對方剛取走的石頭數目的兩倍。

取到最後一顆石頭者獲勝。

問：哪些數字 \(N\)，後取的乙有必勝的策略，又其策略為何？
（第一次接觸的人可以找一個對手玩\(N=30\) 的情形）

淡江大學數學系的余成義教授與師大數學系的鄒永灝同學都曾經研究過這道遊戲，我也是從他們哪兒知道這道遊戲的。從規則看，很難看出遊戲與費波納契數的相關性，但是，經過實際操作之後可以約略領悟費波納契數所扮演的重要性。

事實上，齊肯多夫定理才是這道遊戲必勝策略的總指導。齊肯多夫定理的另一層解釋為「當你手上有 \(1,~2,~3,~5,~8,~13\)

元硬幣各一枚時，你一定可以用他們來湊足所有的數字，不僅湊法唯一，而且使用到的硬幣也不相鄰。」

我們將開始的石頭數目 \(N\) 分成兩類討論如下：

1. 當 \(N\) 是費波納契數時，後玩的乙有必勝的策略。
   其策略就是等甲拿完後，將剩下的石頭一次取完（能夠的話）或者利用齊肯多夫定理（不能夠一次取完的話），將石頭數分解成若干個不相鄰的費波納契數之和，然後拿的石頭數是這分解中最小的費波納契數。然後不斷的重覆這樣的策略，乙就可以拿到最後一顆石頭。
   舉例來說，當 \(N=21\) 時，若甲第一次取 \(8\) 顆石頭，則剩 \(13\) 顆石頭，乙可以一次取完這 \(13\) 顆石頭；但若甲第一次取 \(2\) 顆石頭，則剩 \(19=1+5+13\) 顆石頭，乙只需取最小的 \(1\) 顆石頭，剩 \(18\) 顆石頭，輪到甲，…，最後乙會取走最後一顆石頭。
2. 當 \(N\) 不是費波納契數時，甲可以取走適當的石頭，使得剩下的石頭數目為最靠近 \(N\) 的費波納契數，根據 \((1)\) 的策略，甲變成後完者，會有必勝的策略。例如，當 \(N=30\) 時，甲只需取 \(9\) 顆石頭，就剩下 \(21\) 顆石頭，甲會贏，而 \(f_8=21\)。

當我們把這道遊戲延伸為「每次取的石頭數目不得超過對方剛取走的石頭數目的三倍」時，可能需要另一個數列來扮演費波納契數列的角色，究竟是那個數列呢？

參考文獻

1. 許志農，戲說數學講義。