关于海盗分宝石的题目

今日世界朋友出的题目，和原题目有些出入。原题目的假设条件是投票者不包括分配人。

如果假设条件中，投票者包括分配人。那么在4 号分宝石的时候，推理就出问题了。因为这时候只有两个人，4 号和 5 号，4 号必然投自己的赞成票，那么按题目规定，赞成票已经达到50%，则 4 号的方案必然通过。5 号根本没有任何机会。（100，0）

这样 3 号来分的话，他只需要给 5 号一个宝石，就可以争取到他的票，加上自己的赞成票，2：1，于是通过。（99，0，1）

加入 2 号，为了让自己获得宝石是数目最多，他应该这样分，（99，0，1，0），这样，他可以获得自己的赞成票，和 4 号的赞成票。放弃3 号，5 号。

加入 1 号，应该这样分（98，0，1，0，1）。就可获得自己的票，3 号的票，和 5 号的票。

不知道大家注意到没有，如果包含了自己的票数。那么分配的方案就变得十分简单，自己后一号码的人不给，隔一个给一个。这是因为自己的票数一旦加入，在剩余的人中，只需要少数通过就可以了（加自己，正好半数）。

这样也失去了题目的复杂性。


原题目是这样的：100个宝石，5 个海盗，不变。分配次序不变。条件是：不包括分配者，剩余的人投票，半数及以上通过，则分配。若少于半数同意，则把分配者丢入海里。同时，还有一个重要条件（为什么重要，大家可以仔细想，这里卖个关子）：在利益相同的情况下，海盗倾向于把人丢进海里。


































这样，题目的解答比较复杂了，但基本思想，也就是计算机学里常提到的递归思想：

假设没有123 号，只有 4 5 号，那么无论4 号怎么分，5 号都反对，这样，丢4 号入海，自己全得，还没有潜在威胁。

这时加入3 号。

3 号很清楚，如果4 号不同意自己的分配方案，则自己被丢入海后，就是上面这个情况，4 号必死，所以，无论 3 号怎么分，4 号都必同意，则3 号可以全得宝石，反正能得到 50% 的支持，可以过关。

这时加人2 号。

2 号知道，一旦自己的方案不能通过，则自己被丢入海，上面一种情况发生，3 号可以得到所有宝石。

所以，2 号于是决定放弃 3 号。他只需要给4，5 号一人一颗宝石，就可以了。因为如果 2 号被丢海里，那么就是上面一个情况，4，5号什么也得不到。所以为了确保4，5 号赞成，则必须给他们一人一颗，否则他们非常愿意看2 号喂鲨鱼，呵呵。这样2 号 98 颗，3 号没有，4，5号一人一颗。

这时加入 1 号。

1 号知道，除非自己给 2 号 99 颗，否则2 号是很乐意看到上一种情况发生的，自己也就被丢海里了。而一旦给 2 号 99 颗，票数还是不够。所以，1 号决定放弃 2 号。3 号在上一个情况下，什么也得不到，所以1 号只需要给3 号一个宝石，就足够让他投自己的票。剩下 4，5 号，因为他们可以在上一种情况下每人得一颗宝石，所以必须给他们其中一个人 2 颗宝石，然后放弃另一个。这样，1 号的分配方案应该是：1 号 97 颗，2 号0，3 号 1 颗，4 号 2 颗，5 号 0。这样他起码可以得到 3 号，4 号的赞成票，到了半数，于是通过。（也可以4 号0，5 号 2 颗，一样的）。