以下的想法參考 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) 在某些點的確會有不只一種必勝的移動方法， 但是我的策略所提出的移動方法是最小的 (拿走最少火柴但仍必勝) 以 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)