轉(zhuǎn)載請注明出處:http://www.klion.0fees.net/?p=29

Fibonacci Nim是如下一種游戲

一堆石子有n顆.兩人按如下規(guī)則輪流取一定的石子。

1.第一個取的至少取1顆,至多取n-1顆

2.每次取的石子數(shù)不能超過對手剛?cè)〉?倍,最后取完的算贏家。

現(xiàn)在我們需要算出對于某個n,是先手必勝,還是后手必勝。看到題目,基本也就想到一二了,肯定和Fibonacci數(shù)列有關(guān),確實。不過怎么個有關(guān)法呢？相信只要你動手算幾個小數(shù),就會猜出來了,對于n = Fi先手一定必敗,否則先手必勝。好了，下面我們就來證明這個結(jié)論吧:

首先我們會用到如下三個性質(zhì):

I.若K >= N,則狀態(tài)(N,K)必勝(在這里我們用(N,K)表示還剩下N顆石子,最多能取K顆石子的一個狀態(tài))

II.若狀態(tài)(N,N-1)先手必敗,那么狀態(tài)(N,K)(K<N)必敗。

III.若狀態(tài)(N,K)(K<N)則最后一次取走的石子數(shù)不超過2*N/3

下面證明(Fi,K)(K<Fi)必敗

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

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

設(shè)先手取K顆石子。

  1).若K>=F(i-1)，后手得到狀態(tài)(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)必敗(假設(shè)得到的),所以后手可以使先手達到(F(i),X)(X < F(i))狀態(tài)

  由性質(zhì)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數(shù)就行,這樣就相當(dāng)于后手必輸,也就是先手必勝。