Puzzle

最后一个海盗

黄勇提交的puzzle,我不清楚我的解答是否对，你有兴趣判断一下吧。

5个海盗抢到了100个宝石，然后商量怎样分配，于是抽签派队排出1到5的顺序来提出方案，但是一个条件很重要，就是：提出的方案由大家投票表决来决定，只有“超过”半数的人支持才行，否则，方案判为失败，而提案者要被扔进海里为鲨鱼。于是，由下一个人体方案。即假如第一个人的方案5个人投票没有半数支持，他就被扔进海里喂鲨鱼，然后，由第二个海盗提方案，4个人投票，如果仍未得到半数支持，他也被喂鲨鱼，以此类推。。。

问题：第一个海盗能获得的最佳结果是多少个宝石？

假定：所有的海盗都是智商超群的，知道进退的理性动物，都会理性地分析自己的机会。

要求：1。 不要按照脑筋急转弯的方法去思考，这是生死攸关的问题，没有侥幸。

2。 每个海盗都是杀人成性，贪得无厌的，就像大多数MBA,和CEO一样，只追求更多。

解答：

我的解答被否定了！

两位MBA用“博弈论”和递归方法解决了这个问题：

1。 如果只有两个海盗。那么最后的海盗是稳赢的。1：1

2。 如果只有3个海盗，那么第一个海盗是赢家，因为，第二个海盗一定会帮他。2：1

3。 如果只有4个海盗，那么第一个海盗也是赢家，因为，他会给第3个，第4个海盗各自一个宝石，这样靠着比第二个海盗“仁慈一点”，他可以争取的两个支持者，因为，原来这两个海盗什么也得不到。

4。 如果只有5个海盗，那么第一个海盗也是赢家，因为，要比4个海盗情况下的条件更优惠一些，他给最后一个海盗，和倒数第二个海盗各自2个宝石。

结论：n个海盗的情况，总是第一个海盗是赢家，他只要分析在n-1个海盗情况下每个海盗可能获得的宝石情况里，挑选最少的

n/2或者n/2 + 1（视n的奇偶情况）个海盗，在他们所能得到宝石数加一。（当然，如果n比较大，而宝石数目不够多时候，第一个海盗也活不成了。）

后 记（永不妥协的海盗）

问题似乎解决了，可是我好不甘心，为什么最后的海盗要妥协呢？按照我的想法，最后一个海盗，是最无生命之忧的，他在可以完全保命的情况下，毫无例外地采取他的最优策略---试图杀死所有的海盗，得到所有的宝石，他为什么一定要妥协呢？我的程序原来也是基于这种想法的。

作为商人应该审时度势，因时而变，见好就收，可是对于程序来说，他应该放弃预期中的最大利益而屈就目前的蝇头小利吗？

换种想法，假如5个海盗的情况下，按照MBA的说法，第二个海盗并不是第一个海盗的盟友，相反的第二个海盗有获得98个宝石的利诱，前方百计想要杀死第一个海盗，以便去拿自己的生命来冒险赢取我认为很危险的宝石，这样合理吗？

相反的，最后一个海盗本来是最无生命之虞的却要放弃将来的最大利益来迎合某些小人的龌龊之举？

还是以5个海盗为例子，第一个海盗采取给最后一个和倒数第一个海盗各2个宝石的策略，就一定可以收买得了那最后一个“英明神勇，算无遗策，刚毅果敢，坚定不移”的海盗吗？他为什么不可以继续等小去？既然你们不按照既定的逻辑来玩这个游戏，拿生命开玩笑，那么老衲就陪你们玩下去！你第一个海盗想当然认为我会给你一个宝石所收买，我偏不认账，我不会死，我怕谁？“只有活下去的玩家才有机会！”我可以释放一个信号给第二个海盗：“想收买我吗？请再估估价钱！是钱重要，还是你的命重要？第一个海盗的下场就是你的先例！”

于是，第一个海盗做梦也没有想到自己的如意算盘落了空！投机不成连命都搭上了。等到第二个海盗眼睁睁看着第一个海盗被扔到海里喂鲨鱼了，才醒悟到，自己和第一个海盗都小看了“英明神勇，算无遗策，刚毅果敢，坚定不移”的最后一个海盗，因为，只有他才是处于最有利地位的，失去了同意第一个海盗的分配方案的机会的第二个海盗现在已经走投无路了，因为，排在自己身后的第3个海盗是最凶神恶煞的活阎王，他有着获得100个宝石的机会，决不会被自己所收买，而第四个海盗就算为1个宝石所收买，自己仍旧是2：2。因此，自己活命的机会完全寄托在那“英明神勇，算无遗策，刚毅果敢，坚定不移”的最后一个海盗！

要给他多少他才满足呢？

算了，不开玩笑了，那“英明神勇，算无遗策，刚毅果敢，坚定不移”的最后一个海盗会接受第一个海盗的2个宝石的利诱。

真正的最后答案

今天，收到黄勇的邮件并和他在线讨论，发现两个MBA的解答还不是最优解，虽然他们的理论是正确的，但是答案还不对。

首先，上边的理论是正确的，对于n个海盗，他需要考虑n-1个海盗里每个海盗获利情况，从中挑选出最少的进行排序，

以便在此基础上加一个，而获得他们的支持。在这个游戏里，“没有永远的朋友，也没有永远的敌人，每个人都是按照当

前自己的最大利益行动。”超过一轮的期望值是不算数的。也就是说比如5个海盗的情况下，原本第三个海盗有获得100

个宝石的机会，可是因为要经过两轮，所以，实际是不可能的，他必须放弃这种策略，而改采用更直接的策略就是在第一

轮接受第一个海盗一个宝石的诱惑，同意第一个海盗分配方案。如下：

第一个海盗的分配方案：97， 0， 1， 2， 0 或者 97， 0， 1， 0， 2 。

这种分配方法和以前的分法：96 ，0， 0， 2， 2 的最本质的区别就在于打破了对第三个海盗的一成不变的看法，第

三个海盗并不是愚顽不化的，他也会接受诱惑，因为，超过一轮以上的期望实际是不做数的。怎样理解这一点呢？用反证法！

这个海盗接受不接受这个offer完全取决于它的决定是否对他带来更大的利益。假如第三个海盗不接受，在下一轮里，他的

收益是0，而且这个game就over了，因此，他不会采取对他不利的决策。 而第二个海盗目前是不可收买的，因为，如果他否

决就可以导致这个方案的被推翻，就导致自己成为下一个提案者，而他的宝石期望是最高的，因此，除非他收到比他自己提

建议还多的收益的诱惑，否则他都会表示反对。因此，我们按照n-1个海盗收益从小到大的排序中，他是排在最后的。

相应的，如果讨论6个海盗的情况时候，会有一点点地区别，我们应当把风险因素考虑在内，因为，在6-1=5个海盗的情

况里，有两个方案: 97， 0， 1， 2， 0 或者 97， 0， 1， 0， 2 这两个方案中，最后两个海盗的期望是一个含概率因

素的数学期望，因为两个方案的采用机会均等，最后这两个海盗的获益期望都是：（2+0）/2==1，只要大于他们的期望值

就可以足以产生对他们的吸引力，即 2〉1（这一点我在与黄勇的讨论中也错了，我当时认为是3，没有考虑概率因素。）

所以，分配方案是：95， 0， 1， 2， 2， 0 或者 95， 0， 1， 2， 0， 2。

再进一步的思考是,这个问题为什么会这样复杂？假如我们换个角度来看问题，原本是每次决策就要消灭一个海盗，减少

一个player,而如果是反过来，当初只有一个海盗，每一轮都增加一个海盗来讨论分配问题，思路就明显多了。 因为，在每

加入一个海盗之前，分配的方案是和增加的这个海盗无关的，也就是，比如4个海盗谈论分配的时候，第5个海盗躲在大海上

他能听到其他四个海盗的谈论情况，可是这4个海盗并不知道还有第5个海盗的存在。当第5个海盗突然冒出来讨论分配方案时

前面4个海盗必须决定是坚持原来4个player的策略还是同意这信来的第5个海盗的提议。这样就很清楚了，计算机就不会陷入

我当初担心的逻辑陷阱：每次每个player都预想其他player按照各自的最好策略参加游戏，可是每个player的最好策略又都

受到别人的最好策略的牵制而不断的改变，这每一次的改变导致当初的假设不成立，又要重新修正假设，直到找到平衡。这

种方法看起来可行，实际在计算机的实现是很难的。而根据我的前面的这种基于每个海盗的逻辑顺序的地位，假设他的决策

不影响在他顺序之后的分配情况，问题就简化很多了，最多就是个递推公式而已。