引入
题意:一堆个数为 $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;
}