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

Fibonacci Nim是如下一種游戲

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

1.第一個(gè)取的至少取1顆,至多取n-1顆

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

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

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

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

II.若狀態(tài)(N,N-1)先手必?cái)?那么狀態(tài)(N,K)(K<N)必?cái)　?/p>

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

下面證明(Fi,K)(K<Fi)必?cái)?/p>

一.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.所以后手必勝,也就是先手必?cái)　?/p>

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

    我們可知(F(i-1),K)必?cái)?假設(shè)得到的),所以后手可以使先手達(dá)到(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)必?cái)　?/p>

下面是n != F(i)

那么(N,N-1)先手必勝。這要使得后手處于<=n的最大的Fibonacci數(shù)就行,這樣就相當(dāng)于后手必輸,也就是先手必勝。