轉載請注明出處: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數就行,這樣就相當于后手必輸,也就是先手必勝。