Re: [轉錄] 益智問題（拈 001,100，1枚~3倍）
以下的想法參考 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 的表示法是唯一的
====================================================
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.228.148.169
※ 編輯: stimim 來自: 61.228.148.169 (04/22 00:03)
推
04/22 10:20, , 1F
04/22 10:20, 1F
→
04/22 10:23, , 2F
04/22 10:23, 2F
在某些點的確會有不只一種必勝的移動方法，
但是我的策略所提出的移動方法是最小的 (拿走最少火柴但仍必勝)
以 100 為例子，你可以拿3個來到 (97,3) 也可以拿 24個來到 (76,24)
甚至，如果情況允許，一次拿走 100 根火柴也可以贏
不過，移動到(97,3)是比較可行的，因為有可能你現在是處於 (100,1)的狀態，
也就是此遊戲由 101 根火柴開始，對手拿了一根，輪到你的情況
很顯然的，在此狀況下我們只能拿走3根火柴來獲得勝利。
因此，我所提出的策略是獲得勝利的下限，如果你連我的策略都不可達成
Ex: 97 = 76 + 21 但是你這一輪只能拿 1 ~ 18 個
那很遺憾的，只要對手沒拿錯，你一定輸
※ 編輯: stimim 來自: 61.228.144.78 (04/22 20:29)
討論串 (同標題文章)
完整討論串 (本文為第 9 之 10 篇)：