转载请注明出处:http://www.klion.0fees.net/?p=29

Fibonacci Nim是如下一种游戏

一堆石子有n颗.两人按如下规则轮流取一定的石子。

1.第一个取的至少取1颗,至多取n-1颗

2.每次取的石子数不能超过对手刚取的2倍,最后取完的算赢家。

现在我们需要算出对于某个n,是先手必胜,还是后手必胜。看到题目,基本也就想到一二了,肯定和Fibonacci数列有关,确实。不过怎么个有关法呢？相信只要你动手算几个小数,就会猜出来了,对于n = Fi先手一定必败,否则先手必胜。好了，下面我们就来证明这个结论吧:

首先我们会用到如下三个性质:

I.若K >= N,则状态(N,K)必胜(在这里我们用(N,K)表示还剩下N颗石子,最多能取K颗石子的一个状态)

II.若状态(N,N-1)先手必败,那么状态(N,K)(K<N)必败。

III.若状态(N,K)(K<N)则最后一次取走的石子数不超过2*N/3

下面证明(Fi,K)(K<Fi)必败

一.F1（=2）,F2(=3)显然成立.

二.若F1至Fi成立,则F(i+1)成立

设先手取K颗石子。

  1).若K>=F(i-1)，后手得到状态(N-K,2*K)(N=F(i+1)),2*K>=2*F(i-1)>F(i-1)+F(i-2)=F(i)>N-K.所以后手必胜,也就是先手必败。

 2).若K <= F(i-1)

    我们可知(F(i-1),K)必败(假设得到的),所以后手可以使先手达到(F(i),X)(X < F(i))状态

  由性质III可得X <= (2*F(i-1)/3)*2 = 4*F(i-1)/3 = F(i-1)+1/2*F(i-1) <= F(i-1)+F(i-2)=F(i),所以(F(i),X)必败。

下面是n != F(i)

那么(N,N-1)先手必胜。这要使得后手处于<=n的最大的Fibonacci数就行,这样就相当于后手必输,也就是先手必胜。