威佐夫遊戲
威佐夫遊戲是一個尼姆遊戲(雙人數學博弈遊戲),規則是兩人輪流取兩堆籌碼,其中取法有兩種:取走一堆中任意個籌碼,或從兩堆中取走相同數目的籌碼。取完所有籌碼的一方獲勝。
馬丁·加德納認為威佐夫遊戲在中國稱為「撿石子」[1]。荷蘭數學家威佐夫於1907年發表過一篇論文,從數學角度分析了該遊戲。
![](http://upload.wikimedia.org/wikipedia/commons/thumb/2/2a/Wythoff%27s_Nim.svg/500px-Wythoff%27s_Nim.svg.png)
最佳策略
編輯遊戲過程中的任何狀態都可用一對正整數(n,m)來表示,其中n≤m,分別表示兩堆籌碼的數目。所有狀態分為兩種:先手必勝和後手必勝。在雙方均採取最佳策略的情況下,前者表示下一個行動的玩家將取勝,後者表示下一個行動的玩家將落敗。可見,遊戲的最佳策略是從一個先手必勝狀態移動到任一後手必勝狀態。
對於任一狀態(n,m),可用以下法則遞歸地判斷此狀態是先手必勝還是後手必勝:
- (0,0)為後手必勝狀態。
- 若一個狀態的後續中存在後手必勝狀態,則該狀態為先手必勝。
- 若一個狀態的全部後續均為先手必勝,則該狀態為後手必勝。
例如,由上述第一條、第二條可推出對所有的正整數m,(0,m)和(m,m)均為先手必勝狀態。而(1,2)是後手必勝狀態,因為它的後續(0,1)、(0,2)和(1,1)均為先手必勝狀態。前幾個後手必勝狀態為(0, 0)、(1, 2)、(3, 5)、(4, 7)、(6,10)和(8, 13)。
後手必勝狀態的通式
編輯威佐夫發現後手必勝狀態與黃金分割率有關。具體而言,若k為任意自然數且
其中φ為黃金分割率,中括號表示高斯符號,則(nk,mk)即為第k個後手必勝狀態。這兩個數列在整數數列線上大全中的編號分別為A000201和A001950。
{nk}和{mk}是貝亞蒂列,也即滿足方程
根據貝亞蒂定理,這兩個數列互為補集:所有正整數均僅存在於其中的一個數列並只出現一次。
參見
編輯參考文獻
編輯- ^ Wythoff's game at Cut-the-knot (頁面存檔備份,存於互聯網檔案館), quoting Martin Gardner's book Penrose Tiles to Trapdoor Ciphers