Rules of Fibonacci Game:
最开始可以取1-n-1个石子
以后开始,范围限制在1-opponent取的石子数的两倍
无法按规则取石子则输
结论:
初始状态为Fibonacci数为P状态,否则为N状态.
证明:
证明Fibonacci数为P状态:
1(无法取子,因为取子范围为[1,0],P态)
2(取子范围为[1,1],只能取一个,P态)
3(取子状态为[1,2],不管取子如何,P态)
利用第二类数学归纳法:
设i<n时成立(即,初始态为第i项Fibonacci数:F[i]时成立,i<n)
我们证明i=n(初始态为F[n])时也成立
初始个数F[n]=F[n-1]+F[n-2]
若先手取子数x>=F[n-2]
那么剩下的个数F[n]-F[n-2] <= F[n-1] = F[n-2]+F[n-3] <2*F[n-2] ,但是后手能取的个数范围却是[1,2*F[n-2]],取完,先手败
若先手取子数x<F[n-2],那么剩下的个数 F[n]-F[n-2]>F[n-1], 现在需要证明一种策略把先手导向之前的P态
策略是这样的:
例如对于 Fibonacci数列 1,2,3,5,8,13... 中的13,先手去的个数会小于5,那么剩下的个数会大于8,后手为了赢应该取多少呢? 其实现在的策略跟刚开始有5个石子的时候的策略是一致的(我们对于1,2,3,5,8这样的P态,由归纳法很清楚如果先手取的是x个,我们应该取多少),即总策略是:如何把F[i]的P态导向F[i-1]的P态的策略跟把F[i]-F[i-1]的P态导向一个P态的策略是一致的(看起来是一种递归的策略).
这样我们证明了初始态为自然数中的Fibonacci数是P态.
证明其他初始态为N态,只需要有一种方式导向P太,那就是取石子的个数=初始个数-F[i] , F[i]为与初始态最接近的Fibonacci数.
