海盗分金问题异调

《海盗分金问题异调》由会员分享，可在线阅读，更多相关《海盗分金问题异调（10页珍藏版）》请在装配图网上搜索。

1、 海盗分金问题异调 这是一帮亡命之徒，在海上抢人钱财，夺人性命，干的是刀头上舔血的营生。在我们的印象中，他们一般都瞎一只眼，用条黑布或者讲究点的用个黑皮眼罩把坏眼遮上。他们还有在地下埋宝的好习惯，而且总要画上一张藏宝图，以方便后人掘取。不过大家是否知道，他们是世界上最民主的团体。参加海盗的都是桀骜不驯的汉子，是不愿听人命令的，船上平时一切事都由投票解决。船长的唯一特权，是有自己的一套餐具——可是在他不用时，其他海盗是可以借来用的。船上的唯一惩罚，就是被丢到海里去喂鱼。 现在船上有若干个海盗，要分抢来的若干枚金币。自然，这样的问题他们是由投票来解决的。投票的规则

2、如下：先由最凶猛的海盗来提出分配方案，然后大家一人一票表决，如果 有 50%或以上的海盗同意这个方案，那么就以此方案分配，如果少于 50%的海盗同意，那么这个提出方案的海盗就将被丢到海里去喂鱼，然后由剩下的海盗中最凶猛的那个海盗提出方案，依此类推。 我们先要对海盗们作一些假设。 1) 每个海盗的凶猛性都不同，而且所有海盗都知道别人的凶猛性，也就是说，每个海盗都知道自己和别人在这个提出方案的序列中的位置。另外，每个海盗的数学和逻辑都很好，而且很理智。最后，海盗间私底下的交易是不存在的，因为 第 1 页 海盗除了自己谁都不相信。

3、 2) 一枚金币是不能被分割的，不可以你半枚我半枚。 3) 每个海盗当然不愿意自己被丢到海里去喂鱼，这是最重要的。 4) 每个海盗当然希望自己能得到尽可能多的金币。 5) 每个海盗都是现实主义者，如果在一个方案中他得到了 1 枚金币，而下一个方案中，他有两种可能，一种得到许多金 币，一种得不到金币，他会同意目前这个方案，而不会有侥 幸心理。总而言之，他们相信二鸟在林，不如一鸟在手。 6) 最后，每个海盗都很喜欢其他海盗被丢到海里去喂鱼。在不损害自己利益的前提下，他会尽可能投票让自己的同伴喂鱼。 现在，如果有

4、 10 个海盗要分 100 枚金币，将会怎样？要解决这类问题，我们总是从最后的情形向后推，这样我们就知道在最后这一步中什么是好的和坏的决定。然后运用这个知识，我们就可以得到最后第二步应该作怎样的决定，等 等等等。要是直接就从开始入手解决问题，我们就很容易被 这样的问题挡住去路：“要是我作这样的决定，下面一个海 盗会怎么做？”以这个思路， 先考虑只有 2 个海盗的情况（所 有其他的海盗都已经被丢到海里去喂鱼了） 。记他们为 p1 和 p2，其中 p2 比较凶猛。 p2 的最佳方案当然是： 他自己得 100 枚金币， p1 得 0 枚。

5、投票时他自己的一票就足够 50%了。往 第 2 页 前推一步。现在加一个更凶猛的海盗 p3。 p1 知道—— p3 知 道他知道——如果 p3 的方案被否决了，游戏就会只由 p1 和 p2 来继续，而 p1 就一枚金币也得不到。所以 p3 知道，只要 给 p1 一点点甜头， p1 就会同意他的方案（当然，如果不给 p1 一点甜头，反正什么也得不到， p1 宁可投票让 p3 去喂鱼）。所以 p3 的最佳方案是： p1 得 1 枚， p2 什么也得不到， p3 得 99 枚。 p4 的情况差不多

6、。他只要得两票就可以了，给 p2 一枚金币 就可以让他投票赞同这个方案，因为在接下来 p3 的方案中 p2 什么也得不到。 p5 也是相同的推理方法只不过他要说服 他的两个同伴，于是他给每一个在 p4 方案中什么也得不到 的 p1 和 p3 一枚金币，自己留下 98 枚。 依此类推， p10 的最佳方案是：他自己得 96 枚，给每一个在 p9 方案中什么也得不到的 p2， p4，p6 和 p8 一枚金币。 下面是以上推理的一个表（ y 表示同意， n 表示反对）： 现在我们将海盗分金问题推广： 1) 改变

7、一下规则，投票中方案必须得到超过 50%的票数（只 得到 50%票数的方案的提出者也会被丢到海里去喂鱼） ，那么 如何解决 10 个海盗分 100 枚金币的问题？ 2) 不改变规则，如果让 500 个海盗分 100 枚金币，会发生什么？ 3) 如果每个海盗都有 1 枚金币的储蓄，他可以把这枚金币用 第 3 页 在分配方案中，如果他被丢到海里去喂鱼，那么他的储蓄将 被并在要分配的金币堆中，这时候又怎样？ 通过对规则的细小改变，海盗分金问题可以有许多变化，但 是最有趣的大概是 1

8、) 和 2)（规则仍为 50%票数即可）的情况， 本帖只对这两种情况进行讨论。 首先考虑 1) 。现在只有 p1 和 p2 的情形变得对 p2 其糟无比： 1 票是不够的， 可是就算他把 100 枚金币都给 p1，p1 也照样 会把他丢到海里去。可是 p2 很关键，因为如果 p3 进行分配 方案的话，即使他一枚金币也不给 p2， p2 也会同意，这样 一来 p3 就有 p2 这张铁票！ p3 的最佳方案就是： 独吞 100 枚金币。 p4 要 3 张票，而 p3 是一定反对他的， 而如果不给 p2 一点甜 头， p2 也

9、会反对，因为 p2 可以在 p3 的方案中得救，目前为 什么不把 p4 丢到海里呢？所以要分别给 p1 和 p2 一枚金币， 这样 p4 就有包括他自己 1 票的 3 票。 p4 的方案为： p1， p2 每人 1 枚金币，他自己 98 枚。 p5 的情况要复杂点，他也要 3 票。 p4 是会反对他的，所以 不用给，给 p3 一枚金币就能使他支持自己的方案，因为在 接下来的 p4 方案中他什么也得不到。 问题是 p1 和 p2：只要 其中有一个支持就可以了。可是只给 1 枚金币是不行的， p4 方案中他们一定有 1 枚金币可得，所以

10、只要在他们中随便选 一个，给 2 枚金币，另一个就对不起了，不给。这样 p5 的 第 4 页 方案是：自己 97 枚， p3 得 1 枚， p1 或 p2 得 2 枚。 p6 的方案建立在 p5 的上面，只要给每个 p5 方案中不得益的 海盗 1 枚金币。 要注意的是， p1 和 p2 都应该看作在 p5 方案 中不得益的：他们可能得 2 枚，可是也可能 1 枚不得，所以 只要 p6 给他们 1 枚金币，根据“二鸟在林，不如一鸟在手 “的原则，就可以让他们支持p6 的方案。所以 p6 的方案是 唯一的： p1

11、， p2，p4 每人 1 枚金币， p6 自己拿 97 枚。 这样继续下去， p9 的方案是： p3， p5，p7 每人 1 枚金币，然后在 p1， p2， p4，p6 中任选一人给 2 枚金币， p9 自己得 95 枚。最后， p10 的方案是唯一的： p1，p2，p4，p6，p8 每人 1 枚金币， p10 自己得 95 枚。 2) 是最有趣的（提醒：我们 回到 50%票即可的规则） 。原题解中的推理过程直到 200 个海 盗都是成立的： p200 给每个偶数号的海盗 1 枚金币， 包括他 自己，其他海盗什么也得不到。从 p201 开始，继续推理就

12、 变得有点困难了： p201 为了不被丢到海里去， 必须什么也不 留给自己，而给从 p1 到 p199 中所有奇数号海盗每人 1 枚金 币，从而争取到 100 票，加上他自己 1 票，逃过一劫。 p202 也什么都得不到， 他必须用这 100 枚金币买通 100 个从 p201 的方案中什么也得不到的海盗，要注意到现在这个方案不是 唯一的： p201 的方案中得不到金币的海盗是所有奇数号的海盗，有 101 个（包括 p201），所以有 101 种方案。 p203 必须得到 102 票，除了自己的 1 票外，他只有 100 枚金

13、第 5 页 币，所以只能买到 100 票，所以可怜的家伙就被丢到海里喂 鱼了。但是， p203 是个很重要的角色，因为 p204 知道如果 自己的方案不被通过， p203 也一样会完蛋，所以他有 p203 的一张铁票。所以 p204 可以大出一口气：他自己一票，加 上 p203 一票，然后加上用 100 枚金币买的确 100 票，他就 得救了！ 100 个有幸得到 1 枚金币的海盗， 可以是 p1 到 p202 中任何 100 个：因为其中的偶数号的从 p202 的方案中什么 也得不到，如果 p204 给他们中某个海

14、盗 1 枚金币，这个海 盗一定会赞同这个方案；而编号为奇数的海盗呢，只是有可 能从 p202 的方案中得益罢了（可能性为 100/101 ），所以根 据“二鸟在林，不如一鸟在手“的原则，如果能得到 1 枚金 币，他也会赞同这个方案。 接下去 p205 是不能把希望放在 p203 和 p204 这两张票上的，因为就算他被丢到海里去， p203 和 p204 还可以通过 p204 的方案机会活下来。 p206 虽然可以靠 p205 的铁票，加上自己 1 票和 100 枚金币搞到的 100 票，只有 102 票，所以他也被丢到海里喂鱼。 p207 好不了多少

15、，他需要 104 票，而他自己以及 p205 和 p206 的铁票加上 100 枚金币搞到的 100 票只有 103 票——只好下海。 p208 运气比较好，他同样也要 104 票，可是 p205， p206， p207 都会投票赞成他的方案！加上他自己的 1 票和买来的 第 6 页 100 票，他 于逃脱了做 食的命运。 我 就有了一种可以一直推下去的新 。海盗可以什 么也不留 自己， 上 100 票，然后依靠一部分一定会被 下海的海盗的

16、票，从而 自己的方案通 。有 运气的 海盗分 是 p201， p202， p204， p208，p216， p232， p264， p328 和 p456⋯⋯我 看到 的号 是 200 加上一个 2 的 次 。哪些海盗是受益者呢， 然 票是不用（不能） 金 的。所以只有上一个幸运号 及他以前的那些海盗才有可 能得到 1 枚金 。于是我 得到 500 海盗分 100 枚金 的 是：前 44 个最凶猛的海盗被 海里，然后 p456 给 p1 到 p328 中的 100 个海盗每人 1 枚金 。 就 ，最凶猛的海盗被 海里，而比 凶猛的什么也得 不到，而只有最温柔的那些海盗，才有可能得到 1 枚金 。 第 7 页