前些天中午hzh写在后黑板，说三天后公布答案，结果那天晚上我解出来了，哈哈，挺有意思的一道题目。据说是经济学的经典模型，而且可以延伸出很多问题。原题如下：

有5个海盗他们抢到了100金币，他们从1号开始轮流提出分金方案，如果有一半及以上的人同意这个方案，那么就按这个方案执行，否则将提出方案的这个人投入海中喂鱼。以此类推，假设每个海盗都是绝顶聪明的，那么1号最多能得到多少金币？

受到Matrix67大牛上次那篇There is always a bigger fish的影响，看到海盗分金总是想进行状态转化，于是设海盗数量为n，从1开始推：（设Mi为第i个海盗分到的金币数量）

当n=1时，M1=100

当n=2时，2号海盗必不同意1号的分金方案，1号被杀，转化为n=1的情况，2号海盗得到100金

当n=3时，2号海盗必须同意1号海盗的分金方案（否则若1号被杀，则转化成n=2的情况，2被杀），所以1号提出的方案一定被通过。因此，1号可以提出(M1, M2, M3) = {100, 0, 0}的方案，并得到100金。

麻烦的事情发生在n=4时：

当n=4时，2号必不同意1号的分金方案（如果1被杀了，转化为n=3，2号独吞100金）。现在已经有1个人不同意了，所以1号若是不想被杀，必须买通3号和4号。方法也很简单，{M1, M2, M3, M4} = {98, 0, 1, 1}。很廉价，1金币买通一个人（因为如果3、4拒绝贿赂，那么1被杀，转化成n=3的情况，3、4号一分钱都得不到）。此时，1号最多得到98金。

当n=5时，2号必不同意1号的分金方案（同上，2号希望转化为n=4），1号必须买通3、4（4或5都可）号。因为转化为n=4，2号不会给3号一分钱，所以1号只要用1元钱贿赂他就好了。但是4号有点不好办，转化为n=4，2号会给他1元，要买通他，1号必须出2金。现在1号保证不死了，可以提出(M1, M2, M3, M4, M5) = {97, 0, 1, 2, 0} 或者 {97, 0, 1, 0, 2}。故5海盗分金，1号最多得到97金。

从n=5开始，规律开始出现。我们假设当n=5时1号提出了：

(M1, M2, M3, M4, M5) = {97, 0, 1, 2, 0}，类似的，我们可以推出n=6、7、8、9…的方案：

(                M1, M2, M3, M4, M5) = {                97,  0,  1,  2,  0}
(            M1, M2, M3, M4, M5, M6) = {            96,  0,  1,  2,  0,  1}
(        M1, M2, M3, M4, M5, M6, M7) = {        96,  0,  1,  2,  0,  1,  0}
(    M1, M2, M3, M4, M5, M6, M7, M8) = {    95,  0,  1,  2,  0,  1,  0,  1}
(M1, M2, M3, M4, M5, M6, M7, M8, M9) = {95,  0,  1,  2,  0,  1,  0,  1,  0}

可以看出来M1每隔两位会少1，而(M2, M3, M4)固定是{0, 1, 2}，接下来的就是010101…

易知，这个规律可以坚持到n=196。

至于后面的会发生什么更复杂的事情，可以看看

Comments