Quod Erat Demonstrandum

2016/05/15

和費波那契數列有關的一個遊戲

Filed under: Fun,Junior Form Mathematics — johnmayhk @ 1:39 上午

講開費波那契數列,多談一例。

上次介紹過 nim 這個古舊遊戲,見下:

https://johnmayhk.wordpress.com/2013/06/18/just-a-game/

介紹返,手機 apps 免費玩,搜尋 "nim" 便可(但現世云云手機遊戲,還有小朋友會下載這個嗎?):

johnmayhk-nim-apps

今次把這個 2 人遊戲,略改規則如下:開始時有 n 個包子。第一個玩家至少取一個,但不能全取。之後輪流取包,規則是至少取一個包,也可取任何數目的包,只要取包數目不超過對手之前取包數目的兩倍。取最後一個包者勝。

比如,n = 15,甲乙對賽,甲先取。

甲取 2 個(餘 13 個)
乙不能取多於 4 個,乙取 4 個(餘 9 個)
甲不能取多於 8 個,甲取 1 個(餘 8 個)
乙不能取多於 2 個,乙取 1 個(餘 7 個)
甲不能取多於 2 個,甲取 2 個(餘 5 個)
乙不能取多於 4 個,乙取 3 個(餘 2 個)
甲不能取多於 6 個,甲取 2 個(餘 0 個)
甲勝。

原來如果 n 不是費波那契數,甲有必勝法;但如果 n 是費波那契數,則乙有必勝法。

第一要知,任何正整數必能表達成若干不同的費波那契數之總和,見:

https://johnmayhk.wordpress.com/2012/12/31/sum-of-fibonacci-numbers/

不明白?沒關係,知道實際運作便是了:為方便,先列出費波那契數列:1,1,2,3,5,8,13,21,…

n 是不費波那契數。

舉例,n = 20,那麼少於 20 的最大的費波那契數是 13,即 20 = 13 + 7,而 7 不是費波那契數,少於 7 的最大的費波那契數是 5,即 7 = 5 + 2,而 2 也是費波那契數,完工,即 20 = 13 + 5 + 2。

好了,甲可先取 13,5,2 中最少的數目,即 2 個包,餘 18 個;而乙不能取多於 4 個,所以乙肯定不能全取。乙取(比方說)3 個,餘 15 個,這時,甲又可把 15,用之前的方式,寫成若干不同的費波那契數之總和,即 15 = 13 + 2,故甲可取 13,2 中最少的數目,即 2 個包,餘 13 個,而乙不能取多於 4 個,所以乙肯定不能全取。乙取(比方說)4 個,餘 9 個,這時,甲寫出 9 = 8 + 1,故甲取 1,餘 8,而乙不能取多於 2 個,所以乙肯定不能全取。乙取(比方說)1,餘 7,因 7 = 5 + 2,故甲取 2,餘 5,而乙不能取多於 4 個,所以乙肯定不能全取。乙取(比方說)3 個,餘 2,甲取 2,甲勝。

n 是費波那契數。

甲取若干個包後,餘下的包數若不是費波那契數,只要視乙為第一個玩家,用前段描述的方法,最終乙勝。

甲取若干個包後,餘下的包數若正是費波那契數,舉例,n = 21,甲可取
8 個,餘 13;乙可取 13 而勝;或
13 個,餘 8;乙可取 8 而勝;或
16 個,餘 5;乙可取 5 而勝;或
19 個,餘 2;乙可取 2 而勝;或
20 個,餘 1;乙可取 1 而勝。

數學地證一下。設 n 是第 k 個費波那契數,記曰 n=F_k;而甲取若干包後餘下 m 是第 j 個費波那契數,即 m=F_j,於是甲取包數目是 (n-m)。考慮

2(n-m)=2(F_k-F_j) \geq 2(F_k-F_{k-1})=2F_{k-2}=F_{k-2}+F_{k-2} \geq F_{k-2}+F_{k-3}=F_{k-1} \geq F_j =m

可見餘下的包數 m,一定不超過甲取包數目之兩倍,於是,乙可全取餘下包子獲勝。

最後,如何檢定一個正整數 n 是否費波那契數?只要計算 5n^2+45n^2-4 兩數中若有平方數(perfect square),則 n 是費波那契數。否則就不是。比如 987 是費波那契數嗎?因為 5(987)^2+4=2207^2,所以 987 是費波那契數(其實 987=F_{16})。

參考資料:
https://en.wikipedia.org/wiki/Fibonacci_number
http://superm.math.hawaii.edu/_pdfs/lessons/k_five/SuperM_Nim.pdf

Fibonacci-example-Lovers-Bridge

發表迴響 »

仍無迴響。

RSS feed for comments on this post. TrackBack URI

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 變更 )

Twitter picture

You are commenting using your Twitter account. Log Out / 變更 )

Facebook照片

You are commenting using your Facebook account. Log Out / 變更 )

Google+ photo

You are commenting using your Google+ account. Log Out / 變更 )

連結到 %s

在 WordPress.com 建立免費網站或網誌.

%d 位部落客按了讚: