版權(quán)聲明：轉(zhuǎn)載時(shí)請(qǐng)以超鏈接形式標(biāo)明文章原始出處和作者信息及本聲明
http://yjq24.blogbus.com/logs/46150651.html
有一堆個(gè)數(shù)為n的石子，游戲雙方輪流取石子，滿足：
1)先手不能在第一次把所有的石子取完；
2)之后每次可以取的石子數(shù)介于1到對(duì)手剛?cè)〉氖訑?shù)的2倍之間（包含1和對(duì)手剛?cè)〉氖訑?shù)的2倍）。
約定取走最后一個(gè)石子的人為贏家，求必?cái)B(tài)。
這個(gè)和之前的Wythoff’s Game和取石子游戲有一個(gè)很大的不同點(diǎn)，就是游戲規(guī)則的動(dòng)態(tài)化。之前的規(guī)則中，每次可以取的石子的策略集合是基本固定的，但是這次有規(guī)則2：一方每次可以取的石子數(shù)依賴于對(duì)手剛才取的石子數(shù)。
這個(gè)游戲叫做Fibonacci Nim，肯定和Fibonacci數(shù)列：1,2,3,5,8,13,21,34,55,89,…有密切的關(guān)系。如果試驗(yàn)一番之后，可以猜測(cè)：先手勝當(dāng)且僅當(dāng)n不是Fibonacci數(shù)。必?cái)B(tài)構(gòu)成Fibonacci數(shù)列。
就像“Wythoff博弈”需要“Beatty定理”來(lái)幫忙一樣，這里需要借助“Zeckendorf定理”（齊肯多夫定理）：任何正整數(shù)可以表示為若干個(gè)不連續(xù)的Fibonacci數(shù)之和。定理的證明可以在這里看到，不過(guò)我覺(jué)得更重要的是自己動(dòng)手分解一下。
比如，我們要分解83，可以寫成83=55+28，而28=21+7，7=5+2，故83=55+21+5+2；
如果n=83，我們看看這個(gè)分解有什么指導(dǎo)意義：假如先手取2顆，那么后手無(wú)法取5顆或更多，而5是一個(gè)Fibonacci數(shù)，如果猜測(cè)正確的話，（面臨這5顆的先手實(shí)際上是整個(gè)游戲的后手）那么一定是先手取走這5顆石子中的最后一顆，而這個(gè)我們可以通過(guò)第二類歸納法來(lái)繞過(guò)，同樣的道理，接下去先手取走接下來(lái)的后21顆中的最后一顆，再取走后55顆中的最后一顆，那么先手贏。
反過(guò)來(lái)如果n是Fibonacci數(shù)，比如n=89：如果先手第一次取的石子不小于34顆，那么一定后手贏，因?yàn)?9-34=55=34+21<2*34，所以只需要考慮先手第一次取得石子數(shù)<34即可，于是剩下的石子數(shù)x介于55到89之間，它一定不是一個(gè)Fibonacci數(shù)，于是我們把x分解成Fibonacci數(shù)：x=55+f[i]+…+f[j]，如果f[j]<=先手一開始所取石子數(shù)y的兩倍，那么對(duì)B就是面臨x局面的先手，所以根據(jù)之前的分析，B只要先取f[j]個(gè)即可，以后再按之前的分析就可保證必勝。
下證：f[j]<=2y
反證法：假設(shè)f[j]>2y，則 y<f[j]/2=(f[j-1]+f[j-2])/2<f[j-1]
從而 f[k]=x+y<f[k-1]+f[i]+…+f[j]+f[j-1]<=f[k-1]+f[i]+f[i-1]<=f[k-1]+f[k]=f[k]，矛盾。