挑战≈ 18 分钟未开始
综合挑战:组合博弈
核心概念
本节是组合博弈专题的综合挑战,融合巴什博弈、必胜必败态、对称策略与尼姆游戏。解题时先判断模型:
- 单堆、限制取数 → 巴什博弈(看 的倍数);
- 对称局面(圆桌、等堆) → 对称/镜像策略;
- 多堆任意取 → 尼姆游戏(算尼姆和);
- 全新规则 → 从小局面标注 P/N 找规律。
直观理解 · 动手试试
博弈题的关键是"先认模型,再下结论"。同一道题,认出它是巴什、对称还是尼姆,胜负策略立刻清晰。判断不出来时,就老老实实从最小局面开始标注必胜/必败态,规律往往很快浮现。
即时练习
颗石子,每次取 或 颗,取完者胜,先手必胜。
,,先手必败。
颗石子,每次取 到 颗,先手第一步取几颗才必胜?
,取 颗留 。
尼姆游戏三堆 ,先手必胜。
尼姆和 ,先手必胜。
尼姆游戏两堆各 颗,尼姆和是多少?
,先手必败。
抢 (每次加 或 ,先到 者胜),谁必胜?
后手先手无人必胜取决于运气,等价于巴什必败局面,后手必胜。
两堆石子各 颗,每次从一堆取任意多颗,取完者胜,谁必胜?
后手(镜像策略)先手取决于第一步平局两堆相等,尼姆和为 ,后手镜像必胜。
尼姆和 等于多少?
,。
"必胜态"的正确含义是?
轮到你走,且存在一步走到必败态无论怎么走都赢轮到你走却必输石子最多的局面必胜态 = 能一步把对手逼入必败态的局面。
易错点
- 不先认模型。 先判断是巴什 / 对称 / 尼姆,再套对应结论。
- 尼姆和当普通加法。 异或不进位, 而非 。
- 先后手判断反。 对称(等堆、尼姆和为 0)局面是后手必胜。