海盗分金问题异调

海盗分金问题异调这是一帮亡命之徒，在海上抢人钱财，夺人性命，干的是刀头上舔血的营生。在我们的印象中，他们一般都瞎一只眼，用条黑布或者讲究点的用个黑皮眼罩把坏眼遮上。他们还有在地下埋宝的好习惯，而且总要画上一张藏宝图，以方便后人掘取。不过大家是否知道，他们是世界上最民主的团体。参加海盗的都是桀骜不驯的汉子，是不愿听人命令的，船上平时一切事都由投票解决。船长的唯一特权，是有自己的一套餐具可是在他不用时，其他海盗是可以借来用的。船上的唯一惩罚，就是被丢到海里去喂鱼。现在船上有若干个海盗，要分抢来的若干枚金币。自然，这样的问题他们是由投票来解决的。投票的规则如下：先由最凶猛的海盗来提出分配方案，然后大家一人一票表决，如果有 50%或以上的海盗同意这个方案，那么就以此方案分配，如果少于 50%的海盗同意，那么这个提出方案的海盗就将被丢到海里去喂鱼，然后由剩下的海盗中最凶猛的那个海盗提出方案，依此类推。我们先要对海盗们作一些假设。1) 每个海盗的凶猛性都不同，而且所有海盗都知道别人的凶猛性，也就是说，每个海盗都知道自己和别人在这个提出方案的序列中的位置。另外，每个海盗的数学和逻辑都很好，而且很理智。最后，海盗间私底下的交易是不存在的，因为第 1页海盗除了自己谁都不相信。2) 一枚金币是不能被分割的，不可以你半枚我半枚。3) 每个海盗当然不愿意自己被丢到海里去喂鱼，这是最重要的。4) 每个海盗当然希望自己能得到尽可能多的金币。5) 每个海盗都是现实主义者，如果在一个方案中他得到了1枚金币，而下一个方案中，他有两种可能，一种得到许多金币，一种得不到金币，他会同意目前这个方案，而不会有侥幸心理。总而言之，他们相信二鸟在林，不如一鸟在手。6) 最后，每个海盗都很喜欢其他海盗被丢到海里去喂鱼。在不损害自己利益的前提下，他会尽可能投票让自己的同伴喂鱼。现在，如果有 10 个海盗要分 100 枚金币，将会怎样？要解决这类问题，我们总是从最后的情形向后推，这样我们就知道在最后这一步中什么是好的和坏的决定。然后运用这个知识，我们就可以得到最后第二步应该作怎样的决定，等等等等。要是直接就从开始入手解决问题，我们就很容易被这样的问题挡住去路：“要是我作这样的决定，下面一个海盗会怎么做？”以这个思路， 先考虑只有 2 个海盗的情况（所有其他的海盗都已经被丢到海里去喂鱼了）。记他们为p1 和p2，其中 p2 比较凶猛。 p2 的最佳方案当然是：他自己得 100枚金币， p1 得 0 枚。投票时他自己的一票就足够50%了。往第 2页前推一步。现在加一个更凶猛的海盗p3。 p1 知道 p3 知道他知道如果p3 的方案被否决了，游戏就会只由p1 和p2 来继续，而 p1 就一枚金币也得不到。所以p3 知道，只要给 p1 一点点甜头， p1 就会同意他的方案（当然，如果不给p1 一点甜头，反正什么也得不到， p1 宁可投票让 p3 去喂鱼）。所以 p3 的最佳方案是： p1 得 1 枚， p2 什么也得不到， p3 得99 枚。p4 的情况差不多。他只要得两票就可以了，给p2 一枚金币就可以让他投票赞同这个方案，因为在接下来p3 的方案中p2 什么也得不到。p5 也是相同的推理方法只不过他要说服他的两个同伴，于是他给每一个在p4 方案中什么也得不到的 p1 和 p3 一枚金币，自己留下98 枚。依此类推， p10 的最佳方案是：他自己得96 枚，给每一个在p9 方案中什么也得不到的p2， p4，p6 和 p8 一枚金币。下面是以上推理的一个表（y 表示同意， n 表示反对）：现在我们将海盗分金问题推广：1) 改变一下规则，投票中方案必须得到超过50%的票数（只得到 50%票数的方案的提出者也会被丢到海里去喂鱼），那么如何解决10 个海盗分 100 枚金币的问题？2) 不改变规则，如果让 500 个海盗分 100 枚金币，会发生什么？3) 如果每个海盗都有 1 枚金币的储蓄，他可以把这枚金币用第 3页在分配方案中，如果他被丢到海里去喂鱼，那么他的储蓄将被并在要分配的金币堆中，这时候又怎样？通过对规则的细小改变，海盗分金问题可以有许多变化，但是最有趣的大概是1) 和 2)（规则仍为50%票数即可）的情况，本帖只对这两种情况进行讨论。首先考虑1) 。现在只有 p1 和 p2 的情形变得对p2 其糟无比：1 票是不够的， 可是就算他把100 枚金币都给p1，p1 也照样会把他丢到海里去。可是p2 很关键，因为如果p3 进行分配方案的话，即使他一枚金币也不给p2， p2 也会同意，这样一来 p3 就有 p2 这张铁票！ p3 的最佳方案就是： 独吞 100 枚金币。p4 要 3 张票，而 p3 是一定反对他的， 而如果不给p2 一点甜头， p2 也会反对，因为 p2可以在 p3 的方案中得救，目前为什么不把 p4 丢到海里呢？所以要分别给p1 和 p2 一枚金币，这样 p4 就有包括他自己 1票的 3 票。 p4 的方案为： p1， p2每人 1 枚金币，他自己 98枚。p5 的情况要复杂点，他也要3 票。 p4 是会反对他的，所以不用给，给 p3 一枚金币就能使他支持自己的方案，因为在接下来的 p4 方案中他什么也得不到。问题是 p1 和 p2：只要其中有一个支持就可以了。可是只给1 枚金币是不行的， p4方案中他们一定有 1 枚金币可得，所以只要在他们中随便选一个，给 2 枚金币，另一个就对不起了，不给。这样p5 的第 4页方案是：自己 97枚， p3 得 1 枚， p1 或 p2 得 2 枚。p6 的方案建立在p5 的上面，只要给每个 p5 方案中不得益的海盗 1 枚金币。 要注意的是， p1 和 p2 都应该看作在p5 方案中不得益的：他们可能得2 枚，可是也可能 1 枚不得，所以只要 p6 给他们 1枚金币，根据“二鸟在林，不如一鸟在手“的原则，就可以让他们支持p6 的方案。所以 p6的方案是唯一的： p1， 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 开始，继续推理就变得有点困难了：p201 为了不被丢到海里去，必须什么也不留给自己，而给从p1 到 p199 中所有奇数号海盗每人1 枚金币，从而争取到 100 票，加上他自己 1 票，逃过一劫。 p202 也什么都得不到， 他必须用这 100 枚金币买通 100 个从 p201 的方案中什么也得不到的海盗，要注意到现在这个方案不是唯一的： p201 的方案中得不到金币的海盗是所有奇数号的海盗，有 101 个（包括 p201），所以有 101 种方案。p203 必须得到102 票，除了自己的1 票外，他只有 100 枚金第 5页币，所以只能买到100 票，所以可怜的家伙就被丢到海里喂鱼了。但是， p203 是个很重要的角色，因为p204 知道如果自己的方案不被通过， p203 也一样会完蛋，所以他有p203的一张铁票。所以 p204 可以大出一口气：他自己一票，加上 p203 一票，然后加上用100 枚金币买的确100 票，他就得救了！ 100 个有幸得到1 枚金币的海盗， 可以是 p1 到 p202中任何 100 个：因为其中的偶数号的从p202 的方案中什么也得不到，如果 p204 给他们中某个海盗1 枚金币，这个海盗一定会赞同这个方案；而编号为奇数的海盗呢，只是有可能从 p202 的方案中得益罢了（可能性为100/101 ），所以根据“二鸟在林，不如一鸟在手“的原则，如果能得到1 枚金币，他也会赞同这个方案。接下去 p205 是不能把希望放在 p203 和 p204 这两张票上的，因为就算他被丢到海里去， p203 和 p204 还可以通过 p204 的方案机会活下来。 p206 虽然可以靠 p205 的铁票，加上自己1 票和 100 枚金币搞到的 100 票，只有 102 票，所以他也被丢到海里喂鱼。 p207 好不了多少，他需要 104 票，而他自己以及 p205 和 p206 的铁票加上 100 枚金币搞到的 100 票只有103 票只好下海。p208运气比较好，他同样也要104 票，可是 p205， p206，p207都会投票赞成他的方案！加上他自己的1 票和买来的第 6页100 票，他 于逃脱了做 食的命运。 我 就有了一种可以一直推下去的新 。海盗可以什么也不留 自己， 上100 票，然后依靠一部分一定会被 下海的海盗的 票，从而 自己的方案通 。有 运气的海盗分 是p201， p202， p204， p208，p216， p232， p264，p328 和 p456我 看到 的号 是200 加上一个2 的次 。哪些海盗是受益者呢， 然 票是不用（不能） 金 的。所以只有上一个幸运号 及他以前的那些海盗才有可能得到 1 枚金 。于是我 得到500 海盗分 100 枚金 的 是：前44 个最凶猛的海盗被 海里，然后p456 给 p1到 p328 中的 100 个海盗每人 1 枚金 。就 ，最凶猛的海盗被 海里，而比 凶猛的什么也得不到，而只有最温柔的那些海盗，才有可能得到1 枚金 。第 7页