Table of Contents
题目
桌边坐着两个饥饿的学生Andrea和Bruce，面前有两叠煎饼，高度分别为\(m\)和\(n\)。两人轮流行动：每次必须从较高的那叠中吃掉较低那叠的某个非零整数倍数量的煎饼。每叠最底下那张饼是泡软的，所以谁先吃完任意一叠饼，谁就输。
问：对哪些\((m,n)\)，先手Andrea有必胜策略？如果把输赢规则反过来，先吃完任意一叠饼的人赢，答案又如何？
分析
记黄金比\(\phi=\frac{1+\sqrt{5}}{2}\approx1.618\)。结论非常简洁：
设\(m>n\)。无论"先吃完者输"还是"先吃完者赢"，Andrea必胜当且仅当\(\frac{m}{n}>\phi\)。仅当初始两叠等高时，胜负才取决于输赢规则。
一、强制移动与比值
设当前两叠为\(a,b\)，\(a\ge b\)，记\(r=\frac{a}{b}\)。
- \(a=b\)（\(r=1\)）：只能吃掉整叠。先吃完者输的规则下当前玩家败；先吃完者赢的规则下当前玩家胜。
- \(a\)是\(b\)的倍数（\(r\)为整数）：直接吃到只剩\((b,b)\)即可让对方面对\(r=1\)。因此\(r\)为整数的状态是必胜态。
-
\(1<r<2\)：移动唯一——只能从大叠减一个小叠：\((a,b)\to(b,\,a-b)\)。新比值
\[ r'=\frac{b}{a-b}=\frac{1}{r-1}.\]
玩家别无选择，这是强制移动。
二、黄金比的出现
强制移动的比值变换是\(r\mapsto\frac{1}{r-1}\)。考虑不动点方程\(r=\frac{1}{r-1}\)，即\(r^2-r-1=0\)，正根恰为\(\phi\)。
由于\(\phi\)是无理数而\(r\)总为有理数，\(r\)永远不等于\(\phi\)。因此对任意\(r>1\)，\(r\)和\(\frac{1}{r-1}\)必然分居\(\phi\)两侧：一个大于\(\phi\)，另一个小于\(\phi\)。
这带来了一个极其强大的不变量：
若某玩家面对\(r<\phi\)，他的唯一合法移动必然将\(r\)翻到\(>\phi\)的一侧，还给对手。
反之，若面对\(r>\phi\)，则可能通过选择合适的\(k\)，把\(r<\phi\)的局面丢给对手。
于是游戏变成一场"烫手山芋"的传递：谁被迫接住\(r<\phi\)，谁就只能把\(r>\phi\)扔回去；而接住\(r>\phi\)的人，总能再扔一个\(r<\phi\)回来。分子分母不断减小，最终必然抵达\(r=1\)——谁在\(r=1\)时走棋谁就吃到泡饼。因此：
拥有\(r>\phi\)的一方掌控全局；拥有\(r<\phi\)的一方只能被动跟随。
三、从\(r>\phi\)出发的具体策略
设当前状态为\((m,n)\)，\(m>n\)，且\(\frac{m}{n}>\phi\)。作带余除法\(m=an+b\)（\(0<b<n\)）。注意\(a\ge1\)。
两种有意义的选项：
- 选项A：吃\(an\)个，剩下\((b,n)\)，重排为\((n,b)\)，比值\(\frac{n}{b}\)。
- 选项B：吃\((a-1)n\)个，剩下\((b+n,n)\)，比值\(\frac{b+n}{n}=1+\frac{b}{n}\)。
（吃更少没有好处：留给对手的比值更大，徒增对手的选择余地。）
现在比较\(\frac{n}{b}\)与\(\phi\)：
- 若\(\frac{n}{b}<\phi\)：选A。对手面对比值\(<\phi\)，只能强制走一步，送还一个\(>\phi\)的局面。
- 若\(\frac{n}{b}>\phi\)：选B。注意\(\frac{b}{n}=\frac{1}{n/b}<\frac{1}{\phi}=\phi-1\)，故\(\frac{b+n}{n}=1+\frac{b}{n}<\phi\)。对手面对比值\(<\phi\)，强制移动走到\((n,b)\)（比值\(\frac{n}{b}>\phi\)），又回到你手中——且数字更小了。
无论哪种情形，当前玩家总能在一步或两步之内，让对手面对\(r<\phi\)而自己重新拿到\(r>\phi\)，且堆的高度严格递减。递推下去，直到对手被逼进\(r=1\)，输掉游戏。
这个过程也验证了：所有\(r>\phi\)的状态都是N-position（当前玩家必胜），所有\(1<r<\phi\)的状态都是P-position（当前玩家必败）。
四、先吃完者输 vs 先吃完者赢
以上分析中，唯一用到输赢规则的地方是终点\(r=1\)的判定。而\(r=1\)只有两种到达方式：
- 初始即\(m=n\)：先吃完者输时Andrea必败，先吃完者赢时Andrea必胜。
- 游戏途中由\(r>\phi\)方主动制造：\(\frac{m}{n}\)为整数时，吃掉\(m-n\)个留下\((n,n)\)。先吃完者输时这是获胜手段（给对方泡饼）；先吃完者赢时，对方同样会因为面对\(r=1\)而落败——\(r=1\)时当前玩家被迫吃完整叠，吃到泡饼即输，因此留给对方\(r=1\)同样是获胜手段。
因此，对于所有\(m\neq n\)，两种规则的答案完全一致：Andrea必胜当且仅当\(\frac{m}{n}>\phi\)。
五、实例
-
\((5,3)\)：\(\frac{5}{3}\approx1.667>\phi\)，Andrea必胜。\(5=1\cdot3+2\)，\(\frac{3}{2}=1.5<\phi\)，选A：吃3个留\((3,2)\)。Bruce面对\(r=1.5<\phi\)，被迫走\((2,1)\)。Andrea面对\(r=2>\phi\)，\(2=2\cdot1\)整数，吃1个留\((1,1)\)。Bruce吃到\(r=1\)，输。
-
\((7,5)\)：\(\frac{7}{5}=1.4<\phi\)，Andrea必败。她只能走到\((5,2)\)（\(r=2.5\)）。Bruce面对\(r>\phi\)，\(5=2\cdot2+1\)，\(\frac{2}{1}=2>\phi\)选B：吃2个留\((3,2)\)。Andrea面对\(r=1.5<\phi\)被迫走\((2,1)\)……最终Andrea输。
-
\((11,4)\)：\(\frac{11}{4}=2.75>\phi\)，\(11=2\cdot4+3\)，\(\frac{4}{3}\approx1.33<\phi\)选A：吃8个留\((4,3)\)。Bruce面对\(r<\phi\)，此后Andrea一路掌控。