以下的想法参考 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)