--- description: "5 海盗分 100 金币，最资深者拿 98、隔一人送 1 枚；从 2 人局逆向归纳，超过 200 人时只有 $200+2^k$ 号能活" --- # 5 个海盗分 100 枚金币 ## 题 5 个海盗 A > B > C > D > E（按资历排序）分 100 枚金币。规则： - 最资深的活人提出分配方案，全体（含提议者）投票； - **赞成票至少占一半（含提议者本人）**则通过，按方案分；否则提议者被扔下海，由下一位资深者重新提议。 每个海盗都绝对理性，偏好依次为：**先保命，再多拿金币，两者都一样时宁愿把提议者扔下海**。金币不可分割。A 该怎么提？ ## 一句话 **A 拿 98，C 和 E 各拿 1，B 和 D 拿 0**——方案里没有一处是"公平"，全靠逆向归纳：每个人只比较"这个方案"和"提议者死后我能拿多少"。 ## 关键技巧 **从最小的局倒着推。** 每个人投票时拿当前方案和"提议者被扔下海后的那局"比。所以只要知道 $k-1$ 人局的结果，就能算出 $k$ 人局： - 在 $k-1$ 人局里拿 $x$ 枚的人，现在给他 $x+1$ 枚就能买到他的票（给 $x$ 枚他会投反对——无差别时宁愿杀人）。 - 提议者要凑够票数，就去买**最便宜的票**：那些在下一局里一无所获的人，每票 1 枚。 这是一种博弈里的逆向归纳（backward induction），和[秘书问题](secretary-problem.md)、[掷骰子重投](dice-reroll.md)这类最优停止问题同一个思路：**当下的决策只取决于"之后会怎样"的精确值**。 ## 解 记"剩几个人"为局面。需要的赞成票为 $\lceil k/2 \rceil$（含提议者）。 | 局面 | 提议者 | 需要票数 | 方案（按资历从高到低） | | --- | --- | --- | --- | | D, E | D | 1 | D 100, E 0 | | C, D, E | C | 2 | C 99, D 0, E 1 | | B, C, D, E | B | 2 | B 99, C 0, D 1, E 0 | | A, B, C, D, E | A | 3 | **A 98, B 0, C 1, D 0, E 1** | 逐行看： - **2 人**：D 自己一票就是一半，直接全拿。E 无能为力。 - **3 人**：C 需要 2 票。D 在下一局拿 100，买不起；E 在下一局拿 0，给 1 枚就买到。 - **4 人**：B 需要 2 票。下一局里 D 拿 0，给 D 1 枚。 - **5 人**：A 需要 3 票，自己一票，还要买 2 票。下一局里拿 0 的是 C 和 E，各给 1 枚。 每一步要买的票数恰好等于下一局的"零收入者"人数，所以每一局的方案都是**唯一**的。 ## 延伸 - **规则改成严格过半**：2 人局时 D 需要 2 票，E 一定反对，D 必死——于是在 3 人局里 D 会无条件支持 C，C 拿 100。往上推：4 人局 B 需 3 票，买 D、E 各 1 枚，方案 $98, 0, 1, 1$；5 人局 A 需 3 票，买 C（1 枚）再加 D 或 E 之一（各要 2 枚），方案 $97, 0, 1, 2, 0$ 或 $97, 0, 1, 0, 2$，**不再唯一**。可见"至少一半"还是"严格过半"一字之差，答案整个变了。 - **海盗更多时（至少一半规则）**：$n$ 人局的提议者拿 $100 - \lfloor (n-1)/2 \rfloor$，给与自己同奇偶编号的其余人各 1 枚。$n = 199$、$200$ 时提议者只剩 1 枚；$n = 201$ 时 100 枚全得送出去，自己分文不取也能活。 - **超过 201 人（Stewart, 1999）**：金币不够买票了，关键变成"必死者的票"。$n=203$ 的提议者只有自己一票加 100 枚买来的票，差一票，必死；$n = 204$ 时 203 号为了不死会无条件支持他，刚好够票。继续推，能活的提议者恰好是 $$ n = 200 + 2^k: \quad 201, 202, 204, 208, 216, 232, 264, 328, 456, \ldots $$ 两个幸存编号之间的那些人全部必死——他们的票是下一个幸存者的"免费票"，间隔每次翻倍。 - **常见错误一**：以为 A 要讨好 B。B 在下一局拿 99，买他的票最贵；该买的是下一局里最穷的人。 - **常见错误二**：忘了写"无差别时投反对"。若无差别时投赞成，每个人收 0 枚也肯投票，逐级方案都会变——题目的偏好顺序必须说全。 ??? note "数值验证" 逆向归纳直接编程：每局让提议者按价格从低到高收买票，检查唯一性，再扫描到 600 人找幸存编号。 ```python import math def solve(n, G, need): """海盗编号 1..m，m 最资深、先提议。need(m) = m 人局通过所需票数（含提议者）。 偏好：先保命，再多拿金币，无差别时投反对。plan[m] = 分配 dict，None 表示提议者必死。""" plan = {1: {1: G}} for m in range(2, n + 1): k = m - 1 while plan[k] is None: # m 死后，往下第一个能活的局面 k -= 1 base = plan[k] votes = 1 + (m - 1) - k # 自己 + 夹在中间的必死者（白给的票） short = need(m) - votes if short <= 0: plan[m] = {m: G}; continue prices = sorted((base.get(i, 0) + 1, i) for i in range(1, k + 1)) cost = sum(p for p, _ in prices[:short]) if cost > G: plan[m] = None; continue alloc = {i: p for p, i in prices[:short]} alloc[m] = G - cost alloc['_unique'] = short == len(prices) or prices[short - 1][0] < prices[short][0] plan[m] = alloc return plan half = lambda m: math.ceil(m / 2) # 至少一半（含提议者） strict = lambda m: m // 2 + 1 # 严格过半 for rule, f in (("至少一半", half), ("严格过半", strict)): p = solve(5, 100, f) for m in range(2, 6): a = p[m] if a is None: print(rule, m, "提议者必死"); continue print(rule, m, [a.get(i, 0) for i in range(m, 0, -1)], "唯一" if a.get('_unique', True) else "不唯一") # 至少一半 2 [100, 0] 唯一 # 至少一半 3 [99, 0, 1] 唯一 # 至少一半 4 [99, 0, 1, 0] 唯一 # 至少一半 5 [98, 0, 1, 0, 1] 唯一 # 严格过半 2 提议者必死 # 严格过半 3 [100, 0, 0] 唯一 # 严格过半 4 [98, 0, 1, 1] 唯一 # 严格过半 5 [97, 0, 1, 0, 2] 不唯一 p = solve(600, 100, half) assert all(p[m][m] == 100 - (m - 1) // 2 for m in range(1, 202)) for m in range(2, 201): # 方案唯一，且恰好给同奇偶的人各 1 枚 a = p[m] assert a.get('_unique', True) assert sorted(i for i in a if i not in ('_unique', m) and a[i] > 0) == \ [i for i in range(1, m) if i % 2 == m % 2] print([p[m][m] for m in (5, 10, 50, 199, 200, 201, 202)]) # [98, 96, 76, 1, 1, 0, 0] print([m for m in range(201, 601) if p[m] is not None]) # [201, 202, 204, 208, 216, 232, 264, 328, 456] ``` 200 人以上的部分，代码按一个确定的方案往下推，只用来数票数够不够。这一段谁拿金币不再唯一——提议者可以在多个同价候选人里任选 100 人——Stewart 原文专门处理了这种不确定性，结论同样是幸存编号 $200 + 2^k$。