UOJ Logo wzsyyh的博客

博客

Fibonacci Nim游戏

2021-10-19 19:07:27 By wzsyyh

view in my blog

引入

[COCI2010-2011#4] HRPA

题意:一堆个数为 $n$ 的石子,两人轮流取石子,取走最后一块石子的胜。要求:

  • 先手第一次可取任意多个石子

  • 此外每次可取的石子的个数,至少为 $1$ ,至多为上一轮对方所取个数的 $2$ 倍。

求先手第一次取石子最少取多少可保证获胜。

思考

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

齐肯多夫(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,次小的一堆的最后一块石子一定还是由先手取到,于是先手一定能取到最大的那一堆的最后一块,即整堆石子的最后一块。

CODE

signed main() {
    ll n=gin();
    while(1) {
        if(n==1) {puts("1"); break;}
        if(n==2) {puts("2"); break;}
        ll x=1,y=2,z=3;
        while(z<n) x=y,y=z,z=x+y;
        if(z==n) {printf("%lld\n",z); break;}
        else n-=y;
    }
    return 0;
}
wzsyyh Avatar