威佐夫游戏

威佐夫游戏是一个尼姆游戏（双人数学博弈游戏），规则是两人轮流取两堆筹码，其中取法有两种：取走一堆中任意个筹码，或从两堆中取走相同数目的筹码。取完所有筹码的一方获胜。

马丁·加德纳认为威佐夫游戏在中国称为“捡石子”^[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\,.

根据贝亚蒂定理，这两个数列互为补集：所有正整数均仅存在于其中的一个数列并只出现一次。