挑战≈ 16 分钟未开始
尼姆游戏
核心概念
尼姆(Nim)游戏:有若干堆石子,两人轮流操作,每次从某一堆取走任意多颗(至少 颗),取走最后一颗者胜。
尼姆和:把各堆石子数写成二进制,按位做"异或"(相同为 、不同为 ,即不进位加法),结果叫尼姆和。
判定定理:
- 尼姆和 ⟺ 当前局面是必败态(轮到走的人必输);
- 尼姆和 ⟺ 必胜态,且存在一步把尼姆和变成 。
直观理解 · 动手试试
尼姆游戏的神奇之处,是把"多堆"的复杂博弈压缩成一次二进制按位异或。直觉上,异或为 意味着各堆在每个二进制位上都"成双成对"地平衡——这是一种隐藏的对称。
必胜策略就是永远把局面调回"尼姆和为 ":对手一动,必然打破某一位的平衡(尼姆和变非零),你总能在某一堆里调整,把平衡补回来。如此每轮都把"尼姆和为 "的烫手局面丢给对手,直到对手面对全空(尼姆和为 的终局)而落败。两堆相等时尼姆和为 ,正好解释了上一节"镜像必败"的现象。
尼姆游戏
三堆 3, 4, 5 的尼姆和
第1堆 = 30011
第2堆 = 40100
第3堆 = 50101
异或 =0010 = 2
尼姆和 = 2： ≠ 0,先手必胜(可调整某堆使异或归零)。
3
4
5
按位异或(相同为 0、不同为 1,不进位)。尼姆和为 0 即必败态——各二进制位都成双成对地平衡。
三堆石子 ,求尼姆和并判断先手胜负。
▸查看解答步骤
答: 先手胜(尼姆和=2)
三堆石子 ,先手能必胜吗?
▸查看解答步骤
答: 尼姆和=0,先手败
即时练习
两堆石子 和 ,尼姆和(异或)等于多少?
,。
两堆石子各 颗,先手必胜。
,尼姆和为 ,先手必败(后手镜像)。
三堆石子 ,先手必胜。
尼姆和 ,先手必败。
三堆石子 ,先手必胜。
尼姆和 ,先手必胜。
尼姆游戏中,必败态的判据是?
各堆的尼姆和(异或)为 0各堆石子数之和为偶数堆数为偶数最大堆是最小堆的倍数尼姆和为 即必败态,这是 Bouton 定理。
易错点
- 把异或当成普通加法。 异或是不进位的二进制加法:,不是 。
- 二进制位没对齐。 异或前要把各数右端对齐(按位),位数不同时高位补 。
- 以为石子总数的奇偶决定胜负。 决定胜负的是尼姆和,而非石子总数或堆数。