[数据结构与算法]斐波那契博弈

可能更好的阅读体验

1. 问题

有一堆个数为 $n(n\ge 2)$ 的石子，游戏双方轮流取石子，规则如下：

• 先手不能在第一次把所有的石子取完，至少取 $1$ 颗；
• 在此之后每次可以取的石子数至少为 $1$，至多为对手 刚取的 石子数的 $2$ 倍。

约定取走最后一个石子的人为胜利，求先手何时必胜、必败。

2. 结论与证明

**结论：**当 $n$ 为 $\text{Fibonacci}$ 数的时候先手必败，否则先手必胜。

首先证明当 $n$ 为 $\text{Fibonacci}$ 数的时候先手必败，不妨考虑数学归纳法：

对于 $n=2$ 的情况，显然此时先手必败。

接着不妨设 $n=f_{k?1}$ 之时结论成立，现在我们证明 $n=f_k$ 的情况。此时可以将石子分成 $f_{k?2},f_{k?1}$ 两堆，为啥捏？考虑 $2f_{k?2}>f_k$，所以一旦先手取石子数 $\ge f_{k?2}$，后手就一定能一次取完所有石子。这个结论很重要，也是下文证明的根基。

• 若先手取 $>\frac{1}{3}{f}_{k?2}$ 个石子。此时后手可以取完 $f_{k?2}$ 这个石子堆，并且由于后手取的石子数 $<\frac{2}{3}{f}_{k?2}$，下一轮先手取的石子数也只能 $<\frac{4}{3}{f}_{k?2}=f_{k?2}+\frac{1}{3}{f}_{k?2}$，而 $f_{k?1}=f_{k?2}+f_{k?3}$，且 $\frac{1}{3}{f}_{k?2}<f_{k?4}<f_{k?3}$，所以先手取不完 $f_{k?1}$ 这堆石子。由于 $n=f_{k?1}$ 时结论成立，而且此时先手的选择空间进一步缩小，所以归纳可得 $n=f_k$ 时先手必败。

• 若先手取 $\le \frac{1}{3}{f}_{k?2}$ 个石子。此时可以将 $f_{k?2}$ 这个石子堆分成 $f_{k?4,},f_{k?3}$ 两堆，这是考虑到 $\frac{1}{3}{f}_{k?2}<f_{k?4}$. 然后我们应用上文的结论，同样也可以归纳得到 $n=f_k$ 时先手必败。需要注意的是，上文我们并没有证明后手取完 $f_{k?3}$ 这一堆时的取石子数的范围，但是，由于 $f_{k?3}$ 的下一堆是 $f_{k?1}$，中间一定间隔了编号，所以 $2f_{k?3}<f_{k?1}$，此时先手仍然无法取完 $f_{k?1}$. 这也是下文证明先手必胜情况的依据。

现在证明当 $n$ 不为 $\text{Fibonacci}$ 数的时候先手必胜，需要用到 $\text{Zeckendorf?Theorem}$：任意自然数均可以被分解为若干个 不连续的 $\text{Fibonacci}$ 数之和。

我们先将 $n$ 分解为若干个不连续的 $\text{Fibonacci}$ 数之和，然后取走最小 $\text{Fibonacci}$ 数的石子数。由于不连续，此时后手无法取完任何一个 $\text{Fibonacci}$ 数，这就又回到了 "$n$ 为 $\text{Fibonacci}$ 数的时候先手必败" 的情况。所以此时先手必胜。