智力题之海盗分金
By arthur503 -- 27 Sep 2013
看看智力题真有意思。
查爱奇艺的笔试题的时候，有一道海盗问题，之前看过，再次复习一下。
10个海盗抢到了100张奇艺会员卡，每一张都一样的大小和价值连城，他们决定这样分：
- 1）抽签决定自己的号码（1,2,3,4,5,6,7,8,9,10）；
- 2）首先，由1号提出分配方案，然后大家5人进行表决，当且仅当 超过半数的人同意时按照他的提案进行分配，否则将被扔入大海喂鲨鱼；
- 3）如果1号死后，再由2号提出分配方案， 然后大家4人进行表决，当且仅当 超过半数的人同意时按照他的提案进行分配，否则将被扔入大海喂鲨鱼；
- 4）以此类推。。。。
这个是逆向思维的题目，从第一个海盗的角度来看肯定无法确定如何分配才能让其他人都不反对自己，因此，只能从最后一个人开始想，对于他的最优策略是什么。
如果最后只剩2个人，即：9号和10号，那么无论9号提什么方案，哪怕把东西全给10号，10号也都会反对（条件2：残忍）。因此，9号一定不能让自己来分，所以之前任何的方案他都会同意。
如果最后只剩3个人，那么8号的方案，9号肯定赞成，10号肯定反对，超过一半。所以，对8号的最优分配策略是：100,0,0.
如果最后只剩4个人，那么7号的方案想要获取半数以上通过，必须争取9号、10号的支持（8号是7号死亡后的最大受益者，所以8号肯定会反对）。所以7号只要给9、10号的比8号多一点就可以了。因此，7号最优分配策略是：98,0,1,1.
如果最后只剩5个人，同理，6号也要获取其他2个人的支持，这时有个问题：由于7号是6号死亡的最大获益者，因此7号肯定反对，那么，如何从8、9、10号中选择剩下的两个支持者呢？他们三个在7号的分配方案中收益分别为0,1,1，因此只需比原来的收益高即可。所以，6号的分配方案只需要给其中的两个人加一张卡即可，如：1,2,1；1,1,2；0,2,2.我们此处只以第一个为例（其他亦可），最后6号的分配方案是：96,0,1,2,1.
如果最后剩下6个人，5号需要争取到三个人的支持才行。他只需要在7~10号中选择3位，给比6号多一张卡即可。和之前一样，怎么选择都行，我们只取给前3个号的方案（其他不列出来了），即：93,0,1,2,3,1.
对于4号，需要3个人的支持，从6~10号中选择3人，比5号给的多即可。我们取前3个。因此4号的最优策略是：90,0,1,2,3,3,1.
对于3号，需要4个人的支持，最优策略是：86,0,1,2,3,4,3,1.
对于2号，需要4个人的支持，最优策略是：82,0,1,2,3,4,5,3,1.
对于1号，需要5个人的支持，最优策略是：77,0,1,2,3,4,5,6,3,1.
可以看出来，越往前的人，需要获取的支持人数越多，所以他需要减去所需要获取支持的人数的卡数来给他们每个人多一张的利益。由于如果自己死亡，下一个人是最大受益者，所以不用给他，为0.剩下的人中，挑取需要支持的人数，每人的分配数+1即可。
此处需要注意的是：1.题目是说半数以上的支持才行，因此，对于偶数N个海盗，第一个海盗还需要争取N/2个海盗的支持，也就是总共1+N/2票数；2.对于条件2的理解，海盗都是残忍的人，因此，如果对于1号和2号的分配方案自己的收益都相同，他会选择杀掉1号。因此，1号如果想要获取他的支持，必须要比2号多给。
另外，多说一下，对于注意点2，如果1号、2号的分配方案中自己收益相同，海盗会选择1号的分配方案的话（即不杀掉1号），那么，从6号开始，他只需要给出和7号相同的利益（也就是1张卡）即可。如此类推的话，1号只需要任意选择5个人，每人给1张卡即可获取他们的支持。这是另一种对题目的理解。不过对我而言，我认为是不符合海盗的利益最大化的，因为只有残忍的杀掉前一个相同方案的人，那个人才会为了不被杀掉而给该海盗更多的利益分配。
参考资料：