微软面试题——海盗分金币

Question

被问及微软一个面试题：海盗分金币
5个海盗抢得100枚金币后，讨论如何进行公正分配。他们商定的分配原则是：

（1）抽签确定各人的分配顺序号码（1，2，3，4，5）；

（2）由抽到1号签的海盗提出分配方案，然后5人进行表决，如果方案得到超过半数的人同意，就按照他的方案进行分配，否则就将1号扔进大海喂鲨鱼；

（3）如果1号被扔进大海，则由2号提出分配方案，然后由剩余的4人进行表决，当且仅当超过半数的人同意时，才会按照他的提案进行分配，否则也将被扔入大海；

（4）依此类推。

这里假设每一个海盗都是绝顶聪明而理性，他们都能够进行严密的逻辑推理，并能很理智的判断自身的得失，即能够在保住性命的前提下得到最多的金币。同时还假设每一轮表决后的结果都能顺利得到执行，那么抽到1号的海盗应该提出怎样的分配方案才能使自己既不被扔进海里，又可以得到更多的金币呢？

我的答案是：我用的是倒推法来做。不知道对不对？希望高手帮忙参考下：

4，5分：4提议自己分100个，5没有。5反对，4赞成，通过。3,4,5分：自己99个，5分1个，4没有。3赞成，5觉得1个总比没有强也会同意，4反对无效；2，3,4,5分的话。2分99个，3，5没有，4分一个。2赞成，4知道不同意等3分就什么也没有，所以也同意。3,5反对无效。2个过半，通过。1,2,3,4,5分：1分98个，3,5各分一个。2,4没有。同理，3,5只有同意。所以提议通过。不知道对不对？

Answer 1

倒推法是没错的，但是你的错误是既然自己说“当且仅当超过半数的人同意时，才会按照他的提案进行分配”，那么如果前三个人都被弄死，就算四号把所有金币都给五号，五号一旦不高兴投了反对票，结果将是50%对50%没超过半数，四号依然会死。我的分析如下：
先说四号和三号：四号为了保证自己的绝对安全，就必须在只剩三个人的时候无条件支持三号，即使他一个金币都不给自己，所以三号的方案是（100，0，0），三号给自己投一票，再加上四号的一票，五号就算反对也无济于事。
接下来说二号：既然三号可以独吞100金，所以肯定希望二号去死，那么换言之无论二号拿出什么方案他都会反对，既然如此，就索性一个金币都不给，但他如果想活着，就必须3比1才能行，为此他要讨好四号和五号，怎么讨好？一人一枚金币足矣，为什么呢？因为如果他死了，就会按照刚才说的，四号和五号两个连一枚金币都没有，这样二号的方案是（98，0，1，1）。
最难以分析的是一号：首先他肯定要放弃二号，因为如果想满足二号就必须支付99枚金币，这显然就没法满足利益最大化的要求了。剩下三个人最容易被收买的是三号，刚才说过如果二号有了分配权三号将会一无所有，所以一枚金币就绝对能换来三号的赞成票，然后四号和五号再收买一个就足够了，剩下一个放弃。刚才说二号的方案是（98，0，1，1），所以要两枚金币才能获取他们当中一位的支持。得票情况就是：一号自己一票，三号一票，四号和五号其中一个人会投赞成票，3比2。分配方案是（97，0，1，2，0）或者（97，0，1，0，2）

Answer 2

我看过类似的问题,好像是说大家都是绝对的理性,又想分到绝对多的金币.所以抽到4的不管怎么分.5都要投反对票,4就要扔进大海去喂鱼,全部金子都是5的.说以4一定会保全3,3就提出100.0.0的分法,独吞金币.2是不会同意的说以会投3反对票,提出了100.0.1.1的分法.然后什么分的忘记了反正是一步一步的推过去的,打这么多字累死我了.

Answer 3

简单看一下，这样分有问题，自己分到98个，其他的那么少，你如果是2/3/4/5，你赞成吗？

Answer 4

这就是博弈论总的经典题目
不过、、对了、、是得到超过半数，包括半数吗？？若不含半数的话、、你对的推理就是错的、、、明显你的思维不严谨、、、、、
不含半数的话 剩下45 4稳当被扔进海里 因为他只有半数的票 所以 4不能让3挂掉
而3呢不论提什么方案 4为了保命就得同意 所以3可以得100金 45没有
再说2 他只要给45 一人 1金就可以得到98金 为什么、、因为他们都想得到前面说的和后面说的
接下来是1了 要得钱就得使2个人同意他 哪两个？？ 4和5啊 为什么？因为4是最没有希望发财的所以1金就可以满足他 5呢 也知道这些、、所以他得1金币也就满足了、、所以是 12345 分别 98 0 0 1 1
若含半数的话 才是你的推理
明显当剩下 4和5时 4无论提什么条件 5都得不到好处、、所以3在提条件时只要给5点好处 5肯定会同意、、、同理 2提条件时 给 4点好处 4也会同意、、、这样扩展下去 1只要给3和5点好处 3 5就会同意、、、、、当有X个人时X大于等于3 1只要给奇数号的人好处 这些人都会同意 这样你的答案是正确的、、、这可以