知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 06 - 海盗分金币 ## 题目 5 个海盗抢了 100 枚金币,按从年长到年幼排序(1 号最年长、5 号最年幼)。分金币规则: 1. 从最年长的海盗开始提分配方案 2. 所有海盗(包括提案者自己)投票表决 3. 如果 **≥ 半数**同意(包括正好半数),按方案分配 4. 如果不到半数同意,提案者被扔下海喂鲨鱼,由下一位继续提案 5. 所有海盗都是理性的、贪婪的、嗜血的(在收益相同时会倾向于杀人) 问:1 号海盗的最优分配方案是什么? ## 大白话理解 5 个绝顶聪明的海盗要分赃,提案者必须争取至少一半人支持(包括自己)。如果方案被否决,自己就被喂鲨鱼。每个海盗都极其理性、贪钱、也希望看别人死。 ``` 核心矛盾: 提案者 → 想自己拿最多钱 投票者 → 想让提案者死(分不到钱的话),但如果给的钱够多就支持 关键思维:没法从前到后推 → 必须从后往前逆推! ``` --- ### 逆向递推:从后往前推 #### 如果只剩 5 号(最后一个人) ``` 提案者 = 5 号 总人数 = 1,半数 = 0.5 → 自己投自己就够了 方案:5 号拿 100 枚,自己同意,通过。 5 号:100 ✓ ``` #### 如果剩 {4, 5} 两人 ``` 提案者 = 4 号 总人数 = 2,半数 = 1,需要至少 1 票 4 号投自己 = 1 票 → 已经够半数! 5 号的情况:如果 4 号死了,5 号独吞 100 枚 → 5 号无论如何都不会支持 4 号(因为不同意的话 4 号死,5 号拿 100) 方案:4 号给 5 号 0 枚,自己拿 100,自己同意 → 通过 4 号:100 ✓ 5 号:0 ✗(反对也没用,4 号自己够了) ``` #### 如果剩 {3, 4, 5} 三人 ``` 提案者 = 3 号 总人数 = 3,半数 = 1.5 → 需要 ≥ 2 票 3 号自己投 = 1 票,还需要再拉 1 票。 关键分析——看 4 号和 5 号在"如果 3 号死了"的情况: 4 号:如果 3 死,只剩 4、5,4 号全拿 → 4 号 0 期望 5 号:如果 3 死,只剩 4、5,5 号得 0 → 5 号 0 期望 3 号的策略:用最小的钱收买其中一人。 给 5 号 1 枚 → 5 号:相比"3 死后的 0",多了 1 → 支持 给 4 号 0 枚 → 4 号:反对,但 3+5 已经 2 票,够了 方案:3 号 99 枚,4 号 0 枚,5 号 1 枚 → 通过(3 和 5 同意) 3 号:99 ✓ 4 号:0 ✗ 5 号:1 ✓ ``` #### 如果剩 {2, 3, 4, 5} 四人 ``` 提案者 = 2 号 总人数 = 4,半数 = 2,需要 ≥ 2 票 2 号自己投 = 1 票,还需要拉 1 票。 看 3、4、5 在"如果 2 号死了"的情况(即上一轮的三人局面): 3 号得 99 4 号得 0 5 号得 1 2 号策略:用最小成本收买!给上一轮收益为 0 的人 1 枚就够了。 4 号上一轮得 0 → 给 4 号 1 枚,4 号就会支持(多 1 枚) 方案:2 号 98 枚,3 号 0 枚,4 号 1 枚,5 号 0 枚 → 通过(2 和 4 同意) 2 号:98 ✓ 3 号:0 ✗(虽然反对,但票数不够) 4 号:1 ✓ 5 号:0 ✗ ``` #### 五人全部在:{1, 2, 3, 4, 5} ``` 提案者 = 1 号 总人数 = 5,半数 = 2.5 → 需要 ≥ 3 票 1 号自己投 = 1 票,还需要拉 2 票。 看 2、3、4、5 在"如果 1 号死了"的情况(上一轮): 2 号得 98 3 号得 0 4 号得 1 5 号得 0 1 号策略:收买收益为 0 的那些人,成本最低。 3 号上一轮得 0 → 给 3 号 1 枚 5 号上一轮得 0 → 给 5 号 1 枚 方案:1 号 98 枚,2 号 0 枚,3 号 1 枚,4 号 0 枚,5 号 1 枚 → 通过(1、3、5 同意 = 3 票 ≥ 半数) 1 号:98 ✓ 2 号:0 ✗ 3 号:1 ✓ 4 号:0 ✗ 5 号:1 ✓ ``` --- ### 总结表格 ``` ┌─────────┬───────┬───────┬───────┬───────┬───────┬────────────┐ │ 存活海盗 │ 提案者 │ 1 号 │ 2 号 │ 3 号 │ 4 号 │ 5 号 │ ├─────────┼───────┼───────┼───────┼───────┼───────┼────────────┤ │ 5 │ 5 号 │ --- │ --- │ --- │ --- │ 100 │ │ 4,5 │ 4 号 │ --- │ --- │ --- │ 100 │ 0 │ │ 3,4,5 │ 3 号 │ --- │ --- │ 99 │ 0 │ 1 │ │ 2,3,4,5 │ 2 号 │ --- │ 98 │ 0 │ 1 │ 0 │ │ 1,2,3,4,5│ 1 号 │ 98 │ 0 │ 1 │ 0 │ 1 │ └─────────┴───────┴───────┴───────┴───────┴───────┴────────────┘ ``` --- ### 推广到 N 个海盗、M 枚金币 ``` 如果 N > 2M(海盗比金币多),情况会变: 后面的海盗知道前面的人无论如何凑不够钱收买,他们会一致投反对 → 提案者必死 → 当 N > 2M 时,前面的人都会死,直到人数 ≤ 2M 具体到 100 枚金币: 海盗 N ≤ 200:可以从后往前推,最优方案存在 海盗 N > 200:前 N-200 个提案者必死,直到人数退回 200 ``` --- ## 一句话总结 从后往前递推:只剩 1 人时全拿,每次增加 1 人时,提案者用最小成本(1 枚金币)收买"上一轮收益为 0 的人",凑够半数票。1 号海盗最优方案:自己拿 98,给 3 号和 5 号各 1 枚。 --- 下一篇:[07 - 水壶倒水](./07-water-jug.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入