（本帖改编自《科学美国人》杂志中IanStewart的《凶猛海盗的逻辑》） 　　海盗，大家听说过吧。这是一帮亡命之徒，在海上抢人钱财，夺人性命，干的是刀头 上舔血的营生。在我们的印象中，他们一般都瞎一只眼，用条黑布或者讲究点的用个黑皮 眼罩把坏眼遮上。他们还有在地下埋宝的好习惯，而且总要画上一张藏宝图，以方便後人 掘取。不过大家是否知道，他们是世界上最民主的团体。参加海盗的都是桀骜不驯的汉子 ，是不愿听人命令的，船上平时一切事都由投票解决。船长的唯一特权，是有自己的一套 餐具可是在他不用时，其他海盗是可以借来用的。船上的唯一惩罚，就是被丢到海里去喂 鱼。 　　现在船上有若干个海盗，要分抢来的若干枚金币。自然，这样的问题他们是由投票来 解决的。投票的规则如下︰先由最凶猛的海盗来提出分配方案，然後大家一人一票表决， 如果有50%或以上的海盗同意这个方案，那麽就以此方案分配，如果少于50%的海盗同意， 那麽这个提出方案的海盗就将被丢到海里去喂鱼，然後由剩下的海盗中最凶猛的那个海盗 提出方案，依此类推。 我们先要对海盗们作一些假设。 　　1）每个海盗的凶猛性都不同，而且所有海盗都知道别人的凶猛性，也就是说，每个海 盗都知道自己和别人在这个提出方案的序列中的位置。 　　另外，每个海盗的数学和逻辑都很好，而且很理智。最後，海盗间私底下的交易是不 存在的，因为海盗除了自己谁都不相信。 　　2）一枚金币是不能被分割的，不可以你半枚我半枚。 　　3）每个海盗当然不愿意自己被丢到海里去喂鱼，这是最重要的。 　　4）每个海盗当然希望自己能得到尽可能多的金币。 　　5）每个海盗都是现实主义者，如果在一个方案中他得到了1枚金币，而下一个方案中 ，他有两种可能，一种得到许多金币，一种得不到金币，他会同意目前这个方案，而不会 有侥幸心理。总而言之，他们相信二鸟在林，不如一鸟在手。 　　6）最後，每个海盗都很喜欢其他海盗被丢到海里去喂鱼。在不损害自己利益的前提下 ，他会尽可能投票让自己的同伴喂鱼。 　　现在，如果有10个海盗要分100枚金币，将会怎样？ 　　要解决这类问题，我们总是从最後的情形向後推，这样我们就知道在最後这一步中什 麽是好的和坏的决定。然後运用这个知识，我们就可以得到最後第二步应该作怎样的决定 ，等等等等。要是直接就从开始入手解决问题，我们就很容易被这样的问题挡住去路︰“ 要是我作这样的决定，下面一个海盗会怎麽做？” ============================================================================== 　　以这个思路，先考虑只有2个海盗的情况（所有其他的海盗都已经被丢到海里去喂鱼了 ）。记他们为P1和P2，其中P2比较凶猛。P2的最佳方案当然是︰他自己得100枚金币，P1得 0枚。投票时他自己的一票就足够50%了。 　　往前推一步。现在加一个更凶猛的海盗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表示反对）︰ 　　P1 P2 　　0　100 　　N　Y 　　P1 P2 P3 　　1　0　99 　　Y　N　Y 　　P1 P2 P3 P4 　　0　1　0　99 　　N　Y　N　Y 　　P1 P2 P3 P4 P5 　　1　0　1　0　98 　　Y　N　Y　N　Y 　　…… 　　P1 P2 P3 P4 P5 P6 P7 P8 P9 P10 　　0　1　0　1　0　1　0　1　0　96 　　N　Y　N　Y　N　Y　N　Y　N　Y 　　现在我们将海盗分金问题推广︰ 　　1）改变一下规则，投票中方案必须得到超过50%的票数（只得到50%票数的方案的提出 者也会被丢到海里去喂鱼），那麽如何解决10个海盗分100枚金币的问题？ 　　2）不改变规则，如果让500个海盗分100枚金币，会发生什麽？ 　　3）如果每个海盗都有1枚金币的储蓄，他可以把这枚金币用在分配方案中，如果他被 丢到海里去喂鱼，那麽他的储蓄将被并在要分配的金币堆中，这时候又怎样？ 　　通过对规则的细小改变，海盗分金问题可以有许多变化，但是最有趣的大概是 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的方案是︰自 己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枚金币，所以只能买到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票和买来的100票，他终于逃脱了做鱼食的命运。 　　这样我们就有了一种可以一直推下去的新逻辑。海盗可以什麽也不留给自己，买上100 票，然後依靠一部分一定会被丢下海的海盗的铁票，从而让自己的方案通过。有这样运气 的海盗分别是P201，P202，P204，P208，P216，P232，P264，P328和P456……我们看到这 样的号码是200加上一个2的次幂。 　　哪些海盗是受益者呢，显然铁票是不用（不能）给金币的。所以只有上一个幸运号码 及他以前的那些海盗才有可能得到1枚金币。于是我们得到500海盗分100枚金币的结论是︰ 前44个最凶猛的海盗被丢进海里，然後P456给P1到P328中的100个海盗每人1枚金币。 　　就这样，最凶猛的海盗被丢进海里，而比较凶猛的什麽也得不到，而只有最温柔的那些 海盗，才有可能得到1枚金币。 妈咧个逼！长的要命！... -- ※ Origin: 松涛情怀与斑城故事 <khhs.twbbs.org> ◆ From: u122-206.u61-70.giga.net.tw