zeckendorf定理與Fibonacci博弈

zeckendorf定理：任何正整數可以表示為若干個不連續的Fibonacci數之和

證明：首先，設n為一自然數，m為不大於n的最大Fib數，易知m>n/2。因此將一個數減去不大於其的最大Fib數後，這個數小於原先的1/2。因此可以直接遞降法。

至於不連續，是因為若分出的和有一段連續的Fib數，則可將最大的兩個換為他們的和。

非常naive嗯。。。zeckendorf不愧是業餘初等數論家。。。

PS：明天補與之相關的Fibonacci博弈。。。

———————————————分割線——————————————————————

下面介紹與之相關的Fibonacci博弈

描述：

A，B兩人遊戲：有一堆石子有n個，兩個人輪流從其中取走一定的石子，取走最後所有石子的人為贏家，遵循如下規則：

1.第一次取不能取完,至少取1顆。

2.從第二次開始,每個人取的石子數至少為1,至多為對手剛取的石子數的兩倍。

請問給定n，A是否有必勝策略？（每次A先手）

這是一個組合博弈，組合博弈的具體定義就不細講了，重要的一點是它滿足以下性質：

1.對於接下來行動的玩家，任一局面或為必勝態，或為必敗態。

2.若一個局面其所有後繼局面均為必敗態，則其為必勝態，反之則為必敗態。

對於Fibonacci博弈，先說結論，n為Fib數時A必敗，否則A必勝。

先對較小的n進行驗證，再做歸納假設。

以下為證明：

若n不是Fib數，則n可被分解為多個不連續Fib數，設其可分為a，b，c三堆（a>b>c）

A在第一步先拿走堆c。

考慮誰能先拿完倒數第二堆：設倒數第二堆個數為Fib(n)，首先，因為Fib(n)>2*Fib(n-2)，B不可能一次拿完倒數第二堆。若B拿走的石子數大於等於Fib(n-2)，則剩餘石子必然可被A一次拿完。若B拿走的石子數為x<Fib(n-2)，則有Fib(n)-x必然不是Fib數，將(Fib(n)-x)視作一個子遊戲，由歸納假設知，A必在子遊戲中獲勝。因此無論如何，拿完倒數第二堆的都是A。如此遞推，知A必勝。

證得若n不是Fib數，則A必勝。

在上方對於子遊戲的考慮中，實際已蘊含了證明若n為Fib數，則A必敗。

Q.E.D.

此問題還有進階版本，即K階動態減法問題（把2換做K），做法大致相同。