[COCI2010-2011#4] HRPA

Push_Y · 2021-09-01 14:15:59 · 题解

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

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

齐肯多夫（Zeckendorf）定理

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

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

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

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

证明：

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

• 否则

  • 先取 Fib_{t_1}，其中 t1 满足 Fib_{t_1} < n < Fib_{t_{1} + 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 不为斐波那契数，则将其用齐肯多夫表示法表示后，最小的那一堆个数即为答案。

证明：

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