益智問題（拈之變形） - 拼圖

以下的想法參考 http://zzv.cc/bwxzj (版友 FACE90006 提供的網址)

如果我們把

「輪到你時，不論你可以拿幾個，只要你不拿完，且至少拿一個，你一定輸」

的點列出來，可以得到：

2 3 4 6 8 11 15 21 ...

經過觀察後發現：

2 + 6 = 8
3 + 8 = 11
4 + 11 = 15
6 + 15 = 21

也就是： f(n) = f(n-1) + f(n-4)

為了方便接下來的推論，令

f(0) = 1 , f(1) = 2 , f(2) = 3 , f(3) = 4 , f(4) = 6

f(n≧5)=f(n-1)+f(n-4)

且對於f(n) 和 f(n-4) 我們有： f(n) > 3 * f(n-4)

有了以上的基礎後，"假如"我們可以把某一個數用以下的方式表達

X = f(a1) + f(a2) + f(a3) + f(a4) + ...

且 ak ≦ a(k+1) - 4

且對於每個X，此表達方式是唯一的。

則，當我們碰到剩下X根火柴的狀況，我們就拿走 f(a1) 根火柴，

根據上面推論的結果， f(a1) < 3*f(a2)

因此，對方在下一個回合不可能拿走全部的火柴，也不可能採取和我們一樣的策略

借由這種方式，我們便可以確保對方遲早會走到先手必敗的點，並獲得勝利

====================================================
<證明1>

X = f(a1) + f(a2) + f(a3) + f(a4) + ...

且 ak ≧ a(k+1) + 4

----------------------------------------

對於 X < 10 , 上述成立

假設對於 X < m 皆成立，則當X = m時

if f(k) ≦ m ＜ f(k+1)

則 0 ≦ m - f(k) ＜ f(k+1) - f(k) = f(k-3)

所以：

m = f(k) + m' , which m' ≦ f(k-4)

若 m' 可寫為： f(a2) + f(a3) + ... 且 a2 , a3 ... 的關係滿足 ak ≧ a(k+1) + 4

則令 a1 = k , 必有 a2 + 4 ≦ k = a1 故 X = m 時成立

由數學歸納法得知，對所有的正整數 X 皆成立

=============================================

<證明2>

X 的表示法是唯一的
----------------------------------------------

if X = f(a1) + f(a2) + ... + f(an)

現在我們想要產生一個數列 b1 , b2 ... bm 使得 X = f(b1) + f(b2) + ... + f(bm)

令 M(k) = f(k-1) + f(k-5) + f(k-9) + ...

也就是把所有滿足 k-1 ≧ (k-1) - 4*n ≧ 0 的 f(k-1-4*n) 加起來

=> f(k) > M(k) = f(k-1) + f(k-5) + f(k-9) + ...

因此，X ≧ f(an) > M(an) 而且 M(an) 是使用所有的 f(k<an) 所可以組合出的最大數

因此，不使用f(an) 便不可能產生 X 。

同樣的，沒有f(an-1)不能表示( X-f(an) ) ... 依此類推

故 X 的表示法是唯一的

====================================================

--