知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 12 - 拿石头游戏(巴什博弈) ## 题目 一堆石头,两人轮流取石头,每人每次可以取 **1 颗、2 颗或 3 颗**,取走**最后一颗**的人赢。问:先手有没有必胜策略?必胜策略是什么? ## 大白话理解 你和朋友面前有一堆石头,每人每次可以拿 1~3 颗。谁拿走最后一颗谁赢。 ``` 例:10 颗石头 A 拿 2 颗 → 剩 8 颗 B 拿 3 颗 → 剩 5 颗 A 拿 1 颗 → 剩 4 颗 B 拿 3 颗 → 剩 1 颗 A 拿 1 颗 → A 赢!(A 拿了最后一颗) ``` --- ### 核心推理:必败点分析 ``` 关键:每人每次拿 1~3 颗 → 两人一轮最多拿 1+3 = 4 颗(后手可以控制) 如果轮到某人时,场上恰好剩 4 颗石头,他拿完后剩 1~3 颗, 对手下一轮一定能全部拿完 → 面对 4 颗的人必败! 4 → 必败点 同理推: 如果某人能让对手面对 4 颗 → 自己必胜 要面对 4 颗,自己必须面对 8 颗 → 对手面对 8 颗时,自己可以给他留 4 颗 8 → 必败点(如果轮到对手) 继续推: 要对手面对 8,自己面对 12 12 → 必败点 必败点:4, 8, 12, 16, 20, 24, 28, 32, ... 即:4 的倍数(n % 4 == 0) ``` ``` ASCII 图解: 石子数: 0 1 2 3 4 5 6 7 8 9 10 11 12 ... ─────────────────────────────────────────── 状态: 胜 胜 胜 胜 败 胜 胜 胜 败 胜 胜 胜 败 ... (0颗:已经无石子可取,但轮到的人 ← 上一人被取走了最后一颗 不过通常我们关注"谁取走最后一颗"而非"面对0颗") 修正:考虑"取走最后一颗者赢" 石子数 → 轮到的人 0 颗 → 无石子可取,输(但实际场景不会出现,因为最后一颗已被取走) 1~3 颗 → 全取走,赢! 4 颗 → 无论怎么取,对手面对 1~3 颗,对手赢 → 输! 5~7 颗 → 取 1~3 颗给对手留 4 颗 → 赢! 8 颗 → 对手面对 4 的倍数 → 输! ... 结论:n % 4 == 0 → 先手必败(后手有必胜策略) n % 4 != 0 → 先手必胜(取 n % 4 颗) ``` --- ### 必胜策略 ``` 如果石头总数 n % 4 != 0: 先手取 (n % 4) 颗,使剩余石头变成 4 的倍数 之后,无论对手取 k 颗(1≤k≤3),先手取 4-k 颗 → 每轮两人合计取 4 颗 → 始终保持剩余石头是 4 的倍数 → 最后一轮剩 4 颗时轮到对手 → 对手必败 如果石头总数 n % 4 == 0: 先手必败!无论怎么取,后手都能执行上述策略。 ``` ``` 例:10 颗石头 10 % 4 = 2 → 先手取 2 颗 → 剩 8(4 的倍数) 对手取 1 → 先手取 3 → 剩 4 对手取 2 → 先手取 2 → 剩 4 对手取 3 → 先手取 1 → 剩 4 对手面对 4 → 输了! 例:12 颗石头 12 % 4 = 0 → 先手必败 先手取 1 → 剩 11 → 后手取 3 → 剩 8(给先手留 4 的倍数) 先手取 2 → 剩 10 → 后手取 2 → 剩 8 先手取 3 → 剩 9 → 后手取 1 → 剩 8 ...最终先手面对 4 → 先手输了 ``` --- ### 推广:巴什博弈通用公式 ``` 规则:n 颗石子,每次可取 1~m 颗,取走最后一颗者胜。 必败点分析: 面对 m+1 颗必败(无论怎么取,对手都能取完) → 必败点 = (m+1) 的倍数 必胜策略: if n % (m+1) == 0: 先手必败 else: 先手取 n % (m+1) 颗,之后凑 (m+1) ``` ``` 变体:取走最后一颗者输 必败点规律变了: 面对 1 颗 → 必败(只能取走,然后输) 面对 5 颗 → 必败? → 必败点 = (m+1) 的倍数 + 1 → n % (m+1) == 1 时先手必败 ``` --- ### 延伸到 Nim 博弈 ``` 经典 Nim 游戏:多堆石子 规则: - 每次选一堆,取至少 1 颗 - 取最后一颗者胜 Bouton 定理: 所有堆石子数的异或值 = XOR sum XOR sum == 0 → 当前是必败态 XOR sum != 0 → 当前是必胜态 必胜操作:找一堆 s[i],使得 s[i] XOR (XOR sum) < s[i] 取走差值,使 XOR sum 归零 ``` ```java /** * Nim 游戏:判断先手是否必胜 */ public boolean canWinNim(int[] piles) { int xorSum = 0; for (int p : piles) { xorSum ^= p; } return xorSum != 0; } ``` --- ## 一句话总结 每次可取 1~3 颗时,控制 4 的倍数是关键:若当前石子是 4 的倍数则必败,否则取 `n % 4` 颗后模仿对手凑 4。推广到巴什博弈:每次可取 1~m 颗,`n % (m+1) == 0` 则先手必败。 ---
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入