2008-08-18 5:25| 
10 Comments | 本文内容遵从才知道，海盗分金问题有一个非常有趣的扩展。5个海盗分100个金块不难，100个海盗分100个金块也不难，事实上200个海盗分100个金块也不成问题。有趣的事情发生在第201个海盗身上——为了保命，他连一块金子都不能拿。他不得不把所有100块金子都分给前面199个人中奇数编号的人，从而贿赂他们投他的票（因为在第200个海盗的最优方案中这些人什么都得不到）。加上自己的一票共101票，过半了。同样地，第202个海盗也必须把100块金子分给在第201个海盗的方案中什么也得不到的人，贿赂他们投自己一票。由于第201个海盗的方案中有101个海盗得不到任何东西，因此他的方案不再唯一。加上自己的票共101票，正好是202的一半，这样一来他也活下来了。当问题扩展到N=203时，情况有了戏剧性的变化——第203个海盗无论如何都会死！因为只有100块金子，根本不够他用来贿赂，他无论如何也只能得到101票（别忘了题目条件假设海盗在自身利益相同的情况下会选择杀更多的人）。牛B就牛B在第204个海盗，虽然他也只能贿赂到100票，但是他居然活下来了！你猜他怎么活的？哈哈哈~~~~因为第203个海盗无论如何都会投他一票，不投他的话等轮到自己时就完了。因此第204个海盗把100个金子分给在第202个海盗的方案中啥也得不到的人，加上203和自己的票共102票，这才活了下来。类似地，你会发现第205个海盗必死；第206个海盗虽然会得到205的支持，但是票数仍然不够；207想活的话需要104票，但他也只能搞到103票；208将得到205、206、207的支持，加上自己的一票和贿赂来的100票，正好活了。以后，第216, 232, 264, …, 200+2^n个海盗都将活下来，游戏将在他们这里结束。
10 条回复
您也随便说几句吧：
想当年那个原来的问题我可是研究了好久
科幻世界的某篇文章曾经很讨论到了这一步
其实还有一种扩展，就是投票数量不是大于等于0.5为通过，而是其它的某个数
开头的“煋”什么意思啊……
同问"煋"的问题
偶们初中的数学老师就讲过这个。。。
煋=火星~~~=。=
哦……看出来了……
M牛果然还是文科生
就像这个字一样：饄（这也是一个类文科生告诉我的）
我记得这道题可以扩展到N个海盗分A个金币
最后的结论超过2*A时还是和2的n次幂有关
这个2的n次幂是否跟投票的那个50%有关？能否证明？
厉害
能证明的，比如到第209个海盗的时候，第201~208个海盗就是团结的，因为他们的利益都是0，而海盗都希望别人被扔下海，于是都不会投第209个海盗的支持票。严格的证明正在想。