威佐夫游戏

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

马丁·加德纳认为威佐夫游戏在中国称为“捡石子”Wythoff's game at Cut-the-knot , quoting Martin Gardner's book Penrose Tiles to Trapdoor Ciphers。荷兰数学家于1907年发表过一篇论文，从数学角度分析了该游戏。

 最佳策略 
游戏过程中的任何状态都可用一对正整数(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个后手必胜状态。这两个数列在整数数列线上大全中的编号分别为和。

{nk}和{mk}是贝亚蒂列，也即满足方程

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

 参见 
 尼姆游戏




 参考文献 

 外部链接 

Category:數學遊戲