博弈好难啊啊啊啊啊啊…

斐波那契博弈

描述

1个有n个石子的石堆,两人轮流取.先取者第1次可以取任意多个，但不能全部取完.以后每次取的石子数不能超过上次取子数的2倍，先取完者胜。

结论

如果n是一个斐波那契数，则后手赢，否则先手赢。

证明

首先我们要明确：取石子的时候一定不会取超过剩下的石子的一半，否则下一个人就直接能取完。

当n是一个斐波那契数时，后手赢。(数学归纳法，为方便表示，用$f(x)$来表示第$x$个斐波那契数)

当$n=2$时,显然后手赢，成立。
当$n=3$时,显然后手赢，成立。

假设：n是斐波那契数且$n<=f(k)$时,后手赢。

当$n=f(k+1)$时，将$n$拆成$n=f(k-1)+f(k)$，先手先在$f(k-1)$中拿，且拿不完（拿完后手下次直接就拿完了），由假设可知，后手能拿到$f(k-1)$堆中的最后一个石子。
这里稍微分析一下：后手在$f(k-1)$中能拿到的最多的石子是当且仅当先手先拿$\frac {f(k-1)}3$时，后手拿$\frac{2f(k-1)}3$，易证$\frac{2f(k-1)}3<\frac{f(k)}2$。
此时先手再在$f(k)$堆中拿，且不能一次拿完，就转化成了假设的情况，所以后手赢。

假设正确。

当n不是一个斐波那契数时，先手赢。要借助齐肯多夫定理来证明。

将$n$分解成最大的不连续斐波那契数之和，即$n=f(a_m)+f(a_{m-1})+…+f(a_2)+f(a_1)$。

先手先取最少的一堆，即先取$f(a_1)$这堆，由于是不连续的斐波那契数列，所以$f(a_2)>2f(a_1)$，所以后手只能从$f(a_2)$中拿，且拿不完，这样就转化成了$n$是斐波那契数的情况，所以后手必输。