威佐夫游戏, 是一个尼姆游戏, 双人数学博弈游戏, 规则是两人轮流取两堆筹码, 其中取法有两种, 取走一堆中任意个筹码, 或从两堆中取走相同数目的筹码, 取完所有筹码的一方获胜, 马丁, 加德纳认为在中国称为, 捡石子, 荷兰数学家威佐夫, 英语, willem, abraham, wythoff, 于1907年发表过一篇论文, 从数学角度分析了该游戏, 中的后手必胜状态, 以左下角为原点向右, 上为正方向建立坐标系, 以红色标出的小正方形右上角的顶点坐标即为后手必胜状态, 目录, 最佳策略, 后手必胜状态的通式,. 威佐夫游戏是一个尼姆游戏 双人数学博弈游戏 规则是两人轮流取两堆筹码 其中取法有两种 取走一堆中任意个筹码 或从两堆中取走相同数目的筹码 取完所有筹码的一方获胜 马丁 加德纳认为威佐夫游戏在中国称为 捡石子 1 荷兰数学家威佐夫 英语 Willem Abraham Wythoff 于1907年发表过一篇论文 从数学角度分析了该游戏 威佐夫游戏中的后手必胜状态 以左下角为原点向右 上为正方向建立坐标系 以红色标出的小正方形右上角的顶点坐标即为后手必胜状态 目录 1 最佳策略 2 后手必胜状态的通式 3 参见 4 参考文献 5 外部链接最佳策略 编辑游戏过程中的任何状态都可用一对正整数 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为任意自然数且 n k k ϕ m k ϕ m k displaystyle n k lfloor k phi rfloor lfloor m k phi rfloor m k m k k ϕ 2 n k ϕ n k k displaystyle m k lfloor k phi 2 rfloor lceil n k phi rceil n k k 其中f为黄金分割率 中括号表示高斯符号 则 n k m k 即为第k 个后手必胜状态 这两个数列在整数数列线上大全中的编号分别为A000201和A001950 nk 和 mk 是贝亚蒂列 也即满足方程 1 ϕ 1 ϕ 2 1 displaystyle frac 1 phi frac 1 phi 2 1 根据贝亚蒂定理 这两个数列互为补集 所有正整数均仅存在于其中的一个数列并只出现一次 参见 编辑尼姆游戏 Grundy游戏 英语 Grundy s game 取平方数 英语 Subtract a square 威佐夫矩阵 英语 Wythoff array 参考文献 编辑 Wythoff s game at Cut the knot 页面存档备份 存于互联网档案馆 quoting Martin Gardner s book Penrose Tiles to Trapdoor Ciphers外部链接 编辑埃里克 韦斯坦因 Wythoff s Game MathWorld 取自 https zh wikipedia org w index php title 威佐夫游戏 amp oldid 75023334, 维基百科,wiki,书籍,书籍,图书馆,