如何精确解决所有海盗分金问题的算法及案例？

“五个海盗，100 枚金币，怎么分才能让自己活下来，还拿到最多的钱？” 作为最流行的博弈论题目之一，这道题存在多种规则： 投票门槛怎么定：过半就行，还是必须严格多数？ 海盗的偏好顺序是什么：先保命，再要钱，最后是喜欢杀人，还是讨厌死人？ 经典版：半数及以上通过 这是流传最广的版本，也是大家最熟悉的 98, 0, 1, 0, 1。 规则 只要赞成票达到 一半及以上，方案就通过 海盗都绝顶理性 偏好顺序是： 先活下来 再多拿金币 如果生死和金币都一样，更愿意看到别人死 倒着推 1 人：只剩 E。E 独吞 100。 2 人：D、E。D 只要自己投赞成就够了，因为“半数及以上”意味着 2 人局里 1 票就过。 所以：D=100，E=0 3 人：C、D、E。如果 C 死了，下一轮是 D、E，而 D 会拿 100，E 拿 0。所以 C 只要给 E 1 枚，E 就会支持他。 所以 C=99，D=0，E=1 4 人：B、C、D、E。如果 B 死了，下一轮结果是：C=99，D=0，E=1。4 人局只要 2 票就能过，B 只需要自己再拉 1 票。谁最便宜？当然是 D，因为他下一轮只能拿 0。 所以：B=99，C=0，D=1，E=0 5 人：A、B、C、D、E。如果 A 死了，下一轮结果是：B=99，C=0，D=1，E=0。5 人局要 3 票。A 自己算 1 票，还需要 2 票。最便宜的是谁？C 和 E，因为他们下一轮都只能拿 0。所以 A 只要各给他们 1 枚 答案 A=98，B=0，C=1，D=0，E=1 严格多数版：必须超过半数 这个版本常常被忽略，但它会把答案从 98 改成 97。 规则 把“半数及以上通过”改成： 必须超过半数。 于是： 2 人局需要 2 票 4 人局需要 3 票 5 人局仍需要 3 票 倒着推 1 人：只剩 E。不变。 2 人：D、E。D 需要 2 票，但 E 一定反对，因为 D 一死，E 就独吞 100。所以 D 必死，无论提出什么方案。 3 人：C、D、E。如果 C 死了，会进入 2 人局，而 D 会死，E 独吞 100。所以 D 为了活命，会支持 C，哪怕 0 枚也行。 结果：C=100，D=0，E=0 4 人：B、C、D、E。如果 B 死了，下一轮是：C=100，D=0，E=0。4 人局需要 3 票。B 自己只有 1 票，还得再买 2 票。最便宜的是 D 和 E，各给 1 枚即可。 结果：B=98，C=0，D=1，E=1 5 人：A、B、C、D、E。如果 A 死了，下一轮是：B=98，C=0，D=1，E=1。A 需要再买 2 票。C 给 1 枚就够。而 D 或 E至少有一个人得给 2 枚才会改投 于是 A 的最优方案是： 答案 A=97，B=0，C=1，D=2，E=0 或 A=97，B=0，C=1，D=0，E=2 温和版：海盗不想多死人 前两个版本默认海盗有点“残忍”：如果我活着、拿的钱也一样，那我宁可看你死。但如果最后一条改成： 保命 > 金币 > 少死人 也就是：如果结果对我一样，我更愿意让人活着。这个改动非常致命。在这个场景下，答案不再唯一，且给其他所有人 0 个金币就是其中一种方案。提案者能独吞 100。 假如只剩下 D 和 E，D 只需要自己一票就能独吞金币，E 什么也得不到。 假如剩下 C，D 和 E。即使 C 想要独吞金币，虽然 D 会反对，但 E 会赞成（反正 E 一定拿不到金币且一定活）。 用归纳法看，会更清楚：假设在 \(n-1\) 人局里，首领可以提 100,0,0,...,0 并通过，那么在 \(n\) 人局里，1 号也提 100,0,0,...,0。此时： 2 号 会想：1 号一死，下一轮轮到我，我也能独吞 100，所以我反对。 3 号到 n 号 会想： 1 号死了以后，2 号上位，2 号的方案也还是“自己拿 100，别人 0”； 所以我现在支持 1 号，和我反对 1 号相比，我自己的结局一样：都活，都拿 0。 那我当然选少死一个人，所以投赞成。 于是，当前首领能拿到自己 1 票，3 号到 n 号，一共 (n-2) 票，合计就是 (n-1) 票。这显然足以通过。 答案 若半数同意即可，A 可以直接提：100, 0, 0, 0, 0 若要严格多数同意，除了 2 人局无解外，从 3 人开始，A 也可以独吞 100 金币可无限切分版 如果金币不是整数，而是能分成任意小，比如 0.000001 枚，那收买成本会进一步下降。 以经典版（半数及以上通过）为例，A 原本需要买 C 和 E 两票，各给 1 枚。但如果能无限细分，A 其实只需要给他们“比下一轮多一点点”就够了。 设这个“一点点”为 ε，那么：A = 100 - 2ε，B = 0，C = ε，D = 0，E = ε。A 几乎可以拿走全部金币。 如果海盗人数不断增加 在经典版里： 有 \(n\) 个海盗 有 \(G\) 枚金币 规则是“半数及以上通过” 偏好顺序是“保命 > 金币 > 杀人” 规律和通解 首领不需要说服所有人，只需要说服刚好够用的人。而最便宜的票，永远来自那些在“下一轮”里本来只能拿到 0 的海盗。所以，最优测率：只买下一轮最惨的那几个人，而且每人只多给 1 枚。 把海盗按资历从高到低记作 \(1,2,3,\dots,n\)。 当金币足够时，经典版的最优分配会呈现出这样的形状： \[x_1 = G-(\lceil n/2\rceil-1) \] 而其余海盗中： 第 3 个拿 1 枚 第 5 个拿 1 枚 第 7 个拿 1 枚 …… 其余人都是 0。例如 5 人：\(98,0,1,0,1\) 6 人：\(98,0,1,0,1,0\) 7 人：\(97,0,1,0,1,0,1\) 8 人：\(97,0,1,0,1,0,1,0\) 每增加 2 个海盗，首领就少拿 1 枚金币。这就是经典版最核心的“人数增长规律”。 在海盗不太多时，首领收益按线性下降 由上式可见，首领最终能保住的金币数是： \[G-(\lceil n/2\rceil-1) \] 所以当 \(n\) 增加时，首领收益并不是乱跳的，而是很稳定地下降：下降速度大约是每 2 个海盗损失 1 枚金币。 如果金币固定为 100 枚，那么首领最多只能买出 100 张“1 枚金币的票”。 而经典版中，首领需要的额外票数是：\( \lceil n/2\rceil-1 \)。所以对 100 枚金币而言，只要 \(n\le 202\) 时，将一百个金币分给后面一百个人，虽然首领没有获得金币，但仍能活下来。 到 \(n=203\) 时，就需要 101 张票，第一次不够了。这时，首领无论如何都会死。这时题目的味道就变了：它不再只是“怎么贿选”，而变成了“金币不够时，谁必须先死”。 当海盗比金币还多得多 当海盗数超过 202，首领已经没法靠“每票 1 枚”直接过关。于是最老的海盗会开始死亡，直到局面重新变得可操作。 但是并非只要超过 202 人，首领就一定会死。例如，若海盗数量为 204 人时。我可以给用一百个金币买下 5，7…… 203 号的 100 票，而 2 号海盗即使不给金币也会支持我（否则他会陷入 203 人的必死局），加上自己就可以凑够 102 票了。 我们发现：203 以前，首领主要靠花钱。203 以后，光花钱不够了，于是就出现了新的资源：免费票。所谓“免费票”，就是： 如果我现在不支持你，你死了； 而你一死，下一轮轮到我当首领，但我知道我自己也必死。 那我当然宁愿支持你，让你活，也顺便保住我自己。 这种票不需要 1 枚金币，0 枚就能拿到，因为对方是在“保命”。前面几轮海盗的死亡，会制造出一批免费票或廉价票。 205 人时。如果 1 号死了，下一轮是 204 人局，而 204 我们刚证明了是能活的。所以 2 号不会免费支持 1 号。此时 1 号只能靠自己 + 100 张付费票 = 101 票。显然不够。 206 人时：如果 1 号死了，下一轮是 205 人必死局。所以 2 号知道自己会死，变成1 张免费票。但再往后，205 死掉以后会进入 204，而 204 是能活的，所以只会再多死 2 号，不会继续多出一大串免费票。于是最多票数是：自己 1 + 免费票 1 + 付费票 100 = 合计 102。还是不够。 207 人时：同理，免费票变为 2 张。合计 103。还是差 1。所以 207 仍然不行。 208 人时：如果 1 号死了，会依次进入： 207（不行） 206（不行） 205（不行） 204（行） 这意味着 2 号、3 号、4 号都知道自己会在这一串过程中被处死。 于是 1 号现在拥有：自己 1 票 + 2、3、4 这 3 张免费票 + 100 张付费票 = 104 票。所以 208 又能活。 你会发现，这一段里真正起作用的是：前面连续有多少个必死局”，就会释放出多少张免费票。 设前一个“能活”的人数是 \(s\)。那么比 \(s\) 再多一些人的局面里，如果当前首领死掉，游戏会不断往下掉： \(n-1\) 人局 \(n-2\) 人局 \(n-3\) 人局 …… 一直掉到 \(s\) 人局才重新变成“能活” 这意味着，在 \(n\) 人局里，如果 1 号死了，那么至少前面那一串会在掉落过程中轮流成为首领并被处死的人，都会知道自己反对也活不了，于是他们会给 1 号免费票。共 $ (n-1)-s $ 张。而 1 号还能额外再买 100 张付费票。总票数 $ n - s + 100 $ 因此存活条件是：\( n \ge 2s - 200 \) 这就告诉你：在前一个存活点是 \(s\) 的前提下，下一个存活点是 \(2s-200\)。 因此，超过 202 之后，大多数时候首领一定会死，但是又会出现一串稀疏特别的存活点： 204 人时，首领又能活 208 人时，首领又能活 216 人时，首领又能活 232 人时，首领又能活 264 人时，首领又能活 328 人时，首领又能活