【专题】Fibonacci博弈

Fibonacci博弈

基本的斐波那契博弈（Fibonacci Game）描述如下：

有一堆数量多于一的物品，两人轮流取走物品，第一次至少取一个，但不能取完，从第二次开始每个人最少取一个，最多取对手上次取的两倍。

博弈过程如下：

• 当n为斐波那契数时，令F[k]为斐波那契数第k项，那么当n=2=F[3]，n=3=F[4]显然先手必败，假设n=F[i]，i<k时命题都成立，讨论n=F[k]时，此时n=F[k]=F[k-2]+F[k-1]，由于F[k-1]<2$ \(F[k-2]，所以先手必不能直接取走大于等于F[k-2]的物品，同理先手取走大于等于\) $的物品时，后手可以直接取完F[k-2]，且因 $F[k-1] $ 不会对F[k-1]造成影响，所以每个F[k]可以分解为F[k-2]，F[k-1]这样单独且互不影响的斐波那契局面（可以继续分解）此时先手必败。 得出当n为斐波那契数时先手必败。

• 当n为非斐波那契数时，由齐肯多夫定理，可以将n分解为若干不相邻的斐波那契数之和，例如85=55+21+8+1。此时$ n = F[x_{1}] + F[x_{2}] + + F[x_{k}], (x_{1} > x_{2} > > x_{k})\(，由于\) F[x_{k-1}] > 2 F[x_{k}] \(，取完\) F[x_{k}] \(不会对\) F[x_{k-1}] \(造成影响，即可以分解为若干个单独且互不影响的斐波那契数局面，但先手可以直接取走\) F[x_{k}] $，后手对于每个分解的若干单独且互不影响的斐波那契局面都是必败的。得出当n为非斐波那契数时先手必败。

Zeckendorf定理

Zeckendorf定理：

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

简单证明如下：

• 令F[k]为斐波那契数第k项，那么当n=1=F[1]=F[2]，n=2=F[3]，n=3=F[4]命题成立。假设i<n时命题都成立，讨论i=n时，当n为斐波那契数时，命题显然成立；当n为非斐波那契数时，令k为最大的整数使得F[k]<n<F[k+1]，设m=n-F[k]<(F[k+1]-F[k]=F[k-1])，可得m<F[k-1]<n，由于$ m = F[x_{1}] + F[x_{2}] + + F[x_{k}], (F[x_{k}]最大) \(，因为m<F[k-1]，所以\) x_{k} < k - 1\(，所以\) n = F[x_{1}] + F[x_{2}] + + F[x_{k}] + F[k] \(，仍然可以分解为若干个斐波那契数之和，且不是连续的\) (x_{k} < k - 1) $。