自动搬运

查看原文

来自洛谷，原作者为

	Push_Y 会赢的

搬运于2025-08-24 22:21:16，当前版本为作者最后更新于2021-09-01 14:15:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

建议直接观看我博客中完整的Fibonacci Nim

显然先手可以第一次直接取完获胜，但大多数情况下这么做并不是最少的。下面我们考虑第一次不取完的情况。

齐肯多夫（Zeckendorf）定理

Wikipedia 中对齐肯多夫定理的描述：

任何正整数都可以表示成若干个不连续的斐波那契数之和。

这种和式称为齐肯多夫表述法。

构造这种和式可以通过每次贪心选出最大的不超过它的斐波那契数。

证明：

• 若正整数 $n$ 为斐波那契数，得证。

• 否则

  • 先取 $Fib_{t_1}$，其中 $t1$ 满足 $Fib_{t_1} < n < Fib_{t_{1} + 1}$。

  • $n'=n - Fib_{t_1}$，同上一步取出一个 $Fib_{t_2}$ 满足 $Fib_{t_2} < n' < Fib_{t_{2} + 1}$。

  • 只要证 $t_1 ≠ t_2 + 1$。考虑反证法：

    • 假设 $t_1 = t_2 + 1$，则第一步取出的应当是 $t_1 + 1$ 而不是 $t_1$。原因是 $Fib_{t_1 + 1} = Fib_{t_1} + Fib_{t_1 - 1}$。

解题

引理 1

如果正整数 $n$ 为斐波那契数，则先手必败。

证明：

设 $n = Fib_{t}$，我们把 $n$ 看成 $Fib_{t-1}$ 和 $Fib_{t-2}$ 两堆。

• 若第一步取的个数超过 $Fib_{t-2}$，则后手可以直接取完剩余石子。

• 否则，该问题变成了一个 $n' = Fib_{t-2}$ 的规模更小的同样的问题。

考虑 $n = 2$ 的情况（即规模最小的情况），先手只能取 $1$，于是后手取 $1$ 获胜。

引理 2

如果正整数 $n$ 不为斐波那契数，则将其用齐肯多夫表示法表示后，最小的那一堆个数即为答案。

证明：

$n = f_1 + f_2 + ... + f_k$

先手取完最小的那一堆（即 $f_k$）后，根据齐肯多夫定理，$f_{k-1} > 2 \times f_k$，于是后手无法一次性取完次小的那一堆。再根据引理 1，次小的一堆的最后一块石子一定还是由先手取到，于是先手一定能取到最大的那一堆的最后一块，即整堆石子的最后一块。