威佐夫游戏

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

马丁·加德纳认为威佐夫游戏在中国称为“捡石子”^[1]。荷兰数学家威佐夫（英语：Willem Abraham Wythoff）于1907年发表过一篇论文，从数学角度分析了该游戏。

威佐夫游戏中的后手必胜状态。以左下角为原点向右、上为正方向建立坐标系，以红色标出的小正方形右上角的顶点坐标即为后手必胜状态

最佳策略

游戏过程中的任何状态都可用一对正整数(n,m)来表示，其中n≤m，分别表示两堆筹码的数目。所有状态分为两种：先手必胜和后手必胜。在双方均采取最佳策略的情况下，前者表示下一个行动的玩家将取胜，后者表示下一个行动的玩家将落败。可见，游戏的最佳策略是从一个先手必胜状态移动到任一后手必胜状态。

对于任一状态(n,m)，可用以下法则递归地判断此状态是先手必胜还是后手必胜：

1. (0,0)为后手必胜状态。
2. 若一个状态的后续中存在后手必胜状态，则该状态为先手必胜。
3. 若一个状态的全部后续均为先手必胜，则该状态为后手必胜。

例如，由上述第一条、第二条可推出对所有的正整数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为任意自然数且

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

${\displaystyle 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}是贝亚蒂列，也即满足方程

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

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

参见

• 尼姆游戏
• Grundy游戏（英语：Grundy's game）
• 取平方数（英语：Subtract a square）
• 威佐夫矩阵（英语：Wythoff array）

参考文献

1. Wythoff's game at Cut-the-knot （页面存档备份，存于互联网档案馆）, quoting Martin Gardner's book Penrose Tiles to Trapdoor Ciphers

外部链接

• 埃里克·韦斯坦因. Wythoff's Game. MathWorld.