海盗分金问题--经典智力题推而广之二

《海盗分金问题--经典智力题推而广之二》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、海盗分金问题--经典智力题推而广之二海盗分金问题--经典智力题推而广之二海盗分金问题--经典智力题推而广之二海盗分金问题--经典智力题推而广之二海盗分金问题--经典智力题推而广之二　　海盗，大家听说过吧。这是一帮亡命之徒，在海上抢人钱财，夺人性命，干的是刀头上舔血的营生。在我们的印象中，他们一般都瞎一只眼，用条黑布或者讲究点的用个黑皮眼罩把坏眼遮上。他们还有在地下埋宝的好习惯，而且总要画上一张藏宝图，以方便后人掘取。不过大家是否知道，他们是世界上最民主的团体。参加海盗的都是桀骜不驯的汉子，是不愿听

2、人命令的，船上平时一切事都由投票解决。船长的唯一特权，是有自己的一套餐具——可是在他不用时，其他海盗是可以借来用的。船上的唯一惩罚，就是被丢到海里去喂鱼。　　现在船上有若干个海盗，要分抢来的若干枚金币。自然，这样的问题他们是由投票来解决的。投票的规则如下：先由最凶猛的海盗来提出分配方案，然后大家一人一票表决，如果有50%或以上的海盗同意这个方案，那么就以此方案分配，如果少于50%的海盗同意，那么这个提出方案的海盗就将被丢到海里去喂鱼，然后由剩下的海盗中最凶猛的那个海盗提出方案，依此类推。　　我们先

3、要对海盗们作一些假设。　　1）每个海盗的凶猛性都不同，而且所有海盗都知道别人的凶猛性，也就是说，每个海盗都知道自己和别人在这个提出方案的序列中的位置。　　另外，每个海盗的数学和逻辑都很好，而且很理智。最后，海盗间私底下的交易是不存在的，因为海盗除了自己谁都不相信。　　2）一枚金币是不能被分割的，不可以你半枚我半枚。　　3）每个海盗当然不愿意自己被丢到海里去喂鱼，这是最重要的。　　4）每个海盗当然希望自己能得到尽可能多的金币。　　5）每个海盗都是现实主义者，如果在一个方案中他得到了1枚金币，而下一个

4、方案中，他有两种可能，一种得到许多金币，一种得不到金币，他会同意目前这个方案，而不会有侥幸心理。总而言之，他们相信二鸟在林，不如一鸟在手。　　6）最后，每个海盗都很喜欢其他海盗被丢到海里去喂鱼。在不损害自己利益的前提下，他会尽可能投票让自己的同伴喂鱼。　　现在，如果有10个海盗要分100枚金币，将会怎样？　　要解决这类问题，我们总是从最后的情形向后推，这样我们就知道在最后这一步中什么是好的和坏的决定。然后运用这个知识，我们就可以得到最后第二步应该作怎样的决定，等等等等。要是直接就从开始入手解决问题

5、，我们就很容易被这样的问题挡住去路：”要是我作这样的决定，下面一个海盗会怎么做？”　　以这个思路，先考虑只有2个海盗的情况。记他们为P1和P2，其中P2比较凶猛。P2的最佳方案当然是：他自己得100枚金币，P1得0枚。投票时他自己的一票就足够50%了。　　往前推一步。现在加一个更凶猛的海盗知道——P3知道他知道——如果P3的方案被否决了，游戏就会只由P1和P2来继续，而P1就一枚金币也得不到。所以P3知道，只要给P1一点点甜头，P1就会同意他的方案。所以P3的最佳方案是：P1得1枚，P2什么也得不

6、到，P3得99枚。　　P4的情况差不多。他只要得两票就可以了，给P2一枚金币就可以让他投票赞同这个方案，因为在接下来P3的方案中P2什么也得不到。P5也是相同的推理方法只不过他要说服他的两个同伴，于是他给每一个在P4方案中什么也得不到的P1和P3一枚金币，自己留下98枚。　　依此类推，P10的最佳方案是：他自己得96枚，给每一个在P9方案中什么也得不到的P2，P4，P6和P8一枚金币。　　下面是以上推理的一个表：　　P1P2　　0　100　　N　Y　　P1P2P3　　1　0　99　　Y　N　Y　　

7、P1P2P3P4　　0　1　0　99　　N　Y　N　Y　　P1P2P3P4P5　　1　0　1　0　98　　Y　N　Y　N　Y　　……　　P1P2P3P4P5P6P7P8P9P10　　0　1　0　1　0　1　0　1　0　96　　N　Y　N　Y　N　Y　N　Y　N　Y　　~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~　　现在我们将海盗分金问题推广：　　1）改变一下规则，投票中方案必须得到超过50%的票数，那么如何解决10个海盗分

8、100枚金币的问题？　　2）不改变规则，如果让500个海盗分100枚金币，会发生什么？　　3）如果每个海盗都有1枚金币的储蓄，他可以把这枚金币用在分配方案中，如果他被丢到海里去喂鱼，那么他的储蓄将被并在要分配的金币堆中，这时候又怎样？　　通过对规则的细小改变，海盗分金问题可以有许多变化，但是最有趣的大概是1）和2）的情况，本帖只对这两种情况进行讨论。　　首先考虑1）。现在只有P1和P2的情形变得对P2其糟无比：1票是不够的，可是就算他把100枚金币都给P1，P1也照样会把他丢到海里