brain teasers 学习笔记一

狡猾的海盗

question：海盗们有100个金币，分配原则：最高等级的海盗可以分配所有的硬币，全部海盗（包括最高等级的海盗）拥有投票权，如果百分之五十及以上的海盗投支持票，那么按照最高等级的海盗的分配分配，否则最高等级的海盗被丢进海中，后面第二个等级的海盗变成最高等级的海盗，然后重复之前的过程。如果所有的海盗都是完全理性的，那么最高级海盗在面对船上不同人数的时候应该作出怎样的分配？（考虑海盗人数小于等于100的情况）

answer： 因为每个最高级海盗考虑的分配应该是如果自己被丢下去，船上其他海盗的分配会是怎样，然后收买得不到分配到的人。所以要考虑的是如果有n个人在船上，考虑n-1个人的情况，然后得出分配策略。因此从少考虑到多。
将海盗按等级分，最低的为1，其次为2。
从两个海盗开始考虑：

2个海盗的分配情况

因为会带到海盗2获得自己的1票，1:1。

3个海盗的分配情况

因为会带到海盗3获得海盗3和海盗1的票，2：1。 因为海盗1如果投反对，他将一无所有。

4个海盗的分配情况

因为会带到海盗4获得海盗4和海盗2的票，2：2。因为海盗3一定反对，反对他可以获得99。海盗2 反对将没有，所以收买海盗2。

5个海盗的分配情况

因为会带到海盗5获得海盗5，海盗3和海盗1的票，3：2。

6个海盗的分配情况

因为会带到海盗6获得海盗6，海盗4和海盗2的票，3：3。

因此如果海盗人数是小于100的奇数，最高级海盗会给小于自己的奇数的海盗1个金币，自己拿其他。海盗人数是小于等于100的偶数，最高级海盗会给小于自己的偶数的海盗1个金币，自己拿其他。

reference：A practical guide to quantitative finance interviews