知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 10 - 抢 30 游戏(Nim 博弈入门) ## 题目 两人轮流报数,每次报 **1~3 个数**(比如 A 报 1,2,B 报 3,4,5),谁报到 30 谁赢。问:先手有没有必胜策略?策略是什么? ## 大白话理解 你和朋友玩游戏:从 1 开始数到 30,每人每次可以说 1 到 3 个数,谁数到 30 谁赢。 ``` 示例: A:1, 2(说了 2 个数) B:3, 4, 5(说了 3 个数) A:6(说了 1 个数) ... 谁说到 30 谁赢 ``` --- ### 核心思路:控制步长 ``` 关键观察:每人每次最多说 3 个数,最少说 1 个 如果对方说了 k 个数(1 ≤ k ≤ 3), 我可以补到 4 个数(我说 4 - k 个) 即:无论对方说 1、2 还是 3 个,我总能凑满 4 个。 ``` ``` 逆向推理(从终点回推): 要想抢到 30 → 我必须先抢到 26 (因为我抢到 26 后,对方无论说 1/2/3 个数,都到 27/28/29, 我下一轮就能说到 30) 要想抢到 26 → 必须抢到 22 要想抢到 22 → 必须抢到 18 要想抢到 18 → 必须抢到 14 要想抢到 14 → 必须抢到 10 要想抢到 10 → 必须抢到 6 要想抢到 6 → 必须抢到 2 必胜点:2, 6, 10, 14, 18, 22, 26, 30 这些数 mod 4 都等于 2! ``` ``` 结论:先手先说 2 个数(1, 2),抢到 2。 之后每次对方说 k 个,我说 4-k 个。 保证每 4 个数中最后一个是我说的 → 我终将抢到 30。 如果 30 % (1+3) == 2,先手必胜。 如果 30 % 4 == 0,比如数到 28 谁赢,则先手必败(后手可模仿策略)。 ``` --- ### 推广到通用 Nim 博弈 #### 巴什博弈(Bash Game) ``` 规则:一堆 n 颗石子,两人轮流取 1~m 颗,取走最后一颗者胜。 必胜策略: if n % (m + 1) == 0: 先手必败(无论先手取多少,后手都能凑 (m+1)) else: 先手必胜(先手取 n % (m+1) 颗,之后模仿后手凑 (m+1)) 本题:n=30, m=3 → 30 % 4 = 2 ≠ 0 → 先手必胜,先取 2 ❲ ``` #### 经典 Nim 游戏 ``` 规则:多堆石子,每堆数量任意。两人轮流从某一堆取至少 1 颗, 取走最后一颗者胜。 必胜策略(Bouton 定理): 计算所有堆石子数的异或值(XOR sum) 如果 XOR sum == 0 → 当前是必败态(先手必败) 如果 XOR sum != 0 → 当前是必胜态(先手必胜) 必胜操作:找到一堆,使得取完后 XOR sum = 0 传给对方 ``` ``` 示例: 三堆:{3, 4, 5} XOR = 3 ⊕ 4 ⊕ 5 = 011 ⊕ 100 ⊕ 101 = 010 = 2 ≠ 0 → 必胜 如何取? 对每堆检查:堆的个数 XOR (全部异或) 是否更小 堆 3:3 XOR 2 = 1 < 3 → 可取走 3-1=2 颗,留 1 颗 新状态 {1, 4, 5} → XOR = 1⊕4⊕5 = 0 → 传给对方必败态 ``` --- ### 为什么 Nim 游戏的 XOR = 0 是必败态? ``` 直观理解(不严格): 异或操作在二进制下"不进位加法" XOR = 0 意味着:每个二进制位上,所有堆的该位之和是偶数 如果 XOR = 0: 无论你从哪堆取,必然破坏某个位的平衡 → 新 XOR ≠ 0 → 对方可以恢复平衡 → ... → 直到最后,对方取走最后一颗 如果 XOR ≠ 0: 你一定存在一种取法让 XOR 归零 → 不断把 XOR=0 的必败态丢给对方 ``` --- ### 总结对比 ``` 游戏 策略核心 ────────────────────────────────────────────── 抢 30(每次 1~3) 控制 mod 4 余数 巴什博弈(n 颗,取 1~m) 控制 mod (m+1) Nim(多堆) 异或 XOR = 0 必败 威佐夫博弈(2堆) 黄金分割 φ ``` --- ## 一句话总结 抢 30 的必胜策略:先手说 2(因为 30%4=2),之后无论对方说几个,自己补到 4 个,保证抢到所有 mod 4 == 2 的数。推广到巴什博弈:`n % (m+1) == 0` 先手必败,否则先手必胜。 --- 下一篇:[11 - 过桥/过河问题](./11-cross-bridge.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入