威佐夫遊戲

威佐夫遊戲是一個尼姆遊戲（雙人數學博弈遊戲），規則是兩人輪流取兩堆籌碼，其中取法有兩種：取走一堆中任意個籌碼，或從兩堆中取走相同數目的籌碼。取完所有籌碼的一方獲勝。

馬丁·加德納認為威佐夫遊戲在中國稱為「撿石子」^[1]。荷蘭數學家威佐夫（英語：Willem Abraham Wythoff）於1907年發表過一篇論文，從數學角度分析了該遊戲。

最佳策略

遊戲過程中的任何狀態都可用一對正整數(n,m)來表示，其中n≤m，分別表示兩堆籌碼的數目。所有狀態分為兩種：先手必勝和後手必勝。在雙方均採取最佳策略的情況下，前者表示下一個行動的玩家將取勝，後者表示下一個行動的玩家將落敗。可見，遊戲的最佳策略是從一個先手必勝狀態移動到任一後手必勝狀態。

對於任一狀態(n,m)，可用以下法則遞歸地判斷此狀態是先手必勝還是後手必勝：

例如，由上述第一條、第二條可推出對所有的正整數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為任意自然數且

n_{k}=\lfloor k\phi \rfloor =\lfloor m_{k}\phi \rfloor -m_{k}\,

m_{k}=\lfloor k\phi ^{2}\rfloor =\lceil n_{k}\phi \rceil =n_{k}+k\,

其中φ為黃金分割率，中括號表示高斯符號，則(n_k,m_k)即為第k個後手必勝狀態。這兩個數列在整數數列線上大全中的編號分別為A000201和A001950。

{n_k}和{m_k}是貝亞蒂列，也即滿足方程

{\frac {1}{\phi }}+{\frac {1}{\phi ^{2}}}=1\,.

根據貝亞蒂定理，這兩個數列互為補集：所有正整數均僅存在於其中的一個數列並只出現一次。