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