最近几天看到一个挺有趣的博弈相关的趣谈，今天来分享给大家，并且也会详细讲解最终问题的最优解，并且我还好通过这道题扯一扯递归。
问题描述
有 5 个海盗，获得了 100 枚金币，于是他们要商量一个方法来分配金币。商议方式如下：
由 5 个海盗轮流提出分配方案，规则如下
1、如果超过半数海盗（包括提出者）同意该方案，则按照该方案分配。
2、如果同意该方案的人数（包括提出者）小于等于半数，则提出者要被扔到海里喂鱼，剩下的海盗继续商议分配。
3、海盗们都是绝对聪明理性的，也是绝对贪婪的，以自己尽可能多获得金币为目的。保证自己活命的情况下，且在收益相等的情况下，会倾向把提出者扔到海里。
问：如果你是第一个海盗应该提出怎样的分配方案，才能保证自己既不被扔到海里，又能使自己利益最大化？
解决问题
先做一些假设和提醒
为了方便后面描述，我们假设轮流提出方案的顺序为：海盗1（你），海盗2，海盗3，海盗4，海盗5；也就是说，最开始由海盗1（你） 提出分配方案，海盗5排在最后
并且，大家一定要注意最后一个条件，每个海盗是绝对聪明理性贪婪以及在收益相等的情况下，会倾向把提出者扔到海里。
前方高能，开始扯淡，请你发挥出你的各种猜想
好了，现在如果你是海盗1，你会怎么分配才能使得获得的金币尽可能多，并且不会被扔进海里喂鱼呢？
说实话，第一眼看到这个问题，有点无从下手，脑子太特么乱了，因为完全不知道怎么证明我的分配方案能够让超过一半的海盗都必须支持我，要不平均分配？要不我少一点他们多一点？要不我多一点他们少一点（这样会不会马上就被扔下海里）？
你也可以自己先想几分钟哦，看看你能否自己想的出来？
事实上，要让别人同意我们的想法，我们必须得知彼知己，才能百战百胜。
逐层击破
1、只有 2 个海盗的情况
现在，我们假设只剩两个海盗：海盗4和海盗5，这个时候你应该知道分配结果了吧？
很显然，无论海盗4提出什么方案，海盗5 都会直接拒绝，这样海盗5就可能获得全部的金币了，也就是说，当只有两个海盗时，海盗4无论怎么讨好海盗5，最终的结果都是到海里喂鱼，海盗4绝不敢让海盗3死亡。所以分配结果如下
2、只有3个海盗的情况
这个时候突然跳出了个海盗3，也参与到这场分赃活动中，这个时候海盗3该如何分配？
其实也非常简单，海盗3也知道海盗4心理。他知道如果自己被扔进海里的话，海盗4一定也会被扔进海里，所以海盗3知道，自己无论提出什么方法，海盗4都必须同意，所以海盗3可以提出如下的分配方案：
海盗3： 100 个金币
海盗4： 0 个金币
海盗5： 0 个金币。
也就是，只要海盗4支持海盗3，就可以形成 2：1的局面，海盗3就可以稳赢，不需要兼顾海盗5是否支持。所以最终的分配结果如下
有人可能会说，我们用不用给海盗4分配一点好处？例如分配给海盗4一个金币，条件3有个规则：海盗是贪婪聪明理性的。虽然海盗4没有分配到金币，但是他并没有被扔进海里，这就是最大的好处了
看到这里，你是不是也知道如果是 4 个海盗或者 5 个海盗，你也会分配了？我相信你大概率知道怎么分配了，不过我还是要讲一下，因为后面随着人数的增加，也并没有你想的那么简单，并且后面还会和递归算法串讲一下。
3、只有4个海盗的情况
这个时候又突然蹦出个海盗2，并且海盗2是已经知道了海盗3的分配方案了，这个时候海盗2必须需要获得其中其他2个人的支持。
如何获得其他另2个人的支持？
这很容易，拿点钱给海盗4和海盗5就可以了，海盗2可以提出如下分配方案
海盗2：98个
海盗3：0个
海盗4：1个
海盗5：1个
注意，在收益相等的情况下，海盗们会倾向把提出者扔到海里，所以海盗2必须在海盗3的基础上，多给海盗4和海盗5一个金币，这个时候海盗4和海盗5一定会支持海盗2，因为要是海盗3来提出方案，他们什么都得不到只能保命，还不如同意海盗2的方案。此时的局面是 3：1（支持：反对的人数），因此只有4个人的情况下，海盗2分配方案如上。
有人可能会问，为啥要拉拢贿赂海盗4和海盗5，咱能不能尝试贿赂下海盗3？
答是咱贿赂不起，如果你有这样的想法，只能说明你不是一个合格的海盗！海盗3当时满脑子都是想弄死海盗2，什么贿赂都不会同意海盗2方案的，没必要给他金币。
4、5个海盗的情况
如果有5个海盗，其实海盗1和海盗2一样，只需要拉拢两个人就可以了，那要拉拢谁呢？
这也不难，首先必须得贿赂海盗3，给他一个金币就可以了，因为海盗3知道等海盗2来分配时候自己将一个金币都得不到，只能活命，还不如拿同意海盗1的方案拿1个金币。其次我们在海盗4或者海盗5之中拉拢一个人即可，想要拉拢哪一个，随你开心，所以海盗1可以提出如下方案：
海盗1: 97个
海盗2：0个
海盗3：1个
海盗4和海盗5：其中一个0个，另一个给2个。（他们两个在前面的情况下顶多能拿到1个金币，那当海盗1方案可以给自己分两个金币，那其中拿2个金币的海盗肯定会同意海盗1的方案。作者的建议是给海盗4，因为梦想这种东西海盗5心里可能是一直存在的。而海盗4是5个人里最被动的，能拿到1金币已经喜极而泣了，如今可以分得2个金币，完全会是双手赞成，不然后面的结果不是只能活命就是只能拿一个。）
这样结果将会是3:2通过方案
到这里，就已经分配完毕了，是不是觉得很不可思议？原本还怕自己无论提出啥方案，都会被扔进海里，结果是如此出人意料。以后和别人分赃，是时候拿出这个规则了
问题的核心
有时候遇到这种看似很复杂的博弈问题，不妨先从问题的规模尽量小处理起，后面在逐一增加问题的规模。
不妨来个拓展
如果又突然冒出了一个海盗呢？也就是在一共有 6 个海盗的情况下，该如何处理呢？
有没有觉得，从 5 个到 6 个，是一个分水岭？因为从 5 个开始，就有多种分配方案，这个时候就更加考验你的逻辑了。
不过，对于 6 个，我姑且给大家分析一下，当然，只是我认为是这样，其实我看过别人的也有不同的版本。下面我来分析下（你作为海盗1）可以给出的策略：
首先，我们必须拉拢 3 个人，结果必须至少4:2显然，我们是不可能会拉拢海盗2（即5个海盗中的海盗1）因为咱拉不起。他巴不得你喂鱼呀。因为我们会从海盗3~ 海盗6中考虑。
1、首先我们必须拉拢海盗3（前面情况中的海盗2），因为他最容易贿赂，给他 1 个金币即可，因为如果你没了，剩5个人时候，海盗2来分配（即上述分配方案）他将一个金币拿不到。
2、接着，我们拉拢海盗4（前面情况的海盗3），给他两个金币即可，等海盗2分配方案中他只能拿1个。还不如此刻拿2个
此时，我们已经拉拢了海盗3和海盗4，接下来我们需要在海盗5和海盗6中选一个即可，那么问题来了，该给海盗5和海盗6他们多少，他们才愿意同意你的方案？
显然，如果我们给海盗5分配 3 个金币，海盗6分配 0 个，显然海盗5一定会同意。
但是，真的需要给海盗5分配 3 个吗？如果我给他 2 个金币，他会同意吗？
答是会的，为什么呢？因为在5个海盗分配的方案中，海盗5（即前面的海盗4）最多拿2个，且具有不确定性，因为海盗2方案可以在最后两个海盗中2选一给2个金币。如今你的方案可以让他自己可以稳拿2个金币，后面的分配结果不会比这更多了，还有分不到的风险。那海盗5是6个人里面最被动的人，稳拿2个金币的方案中下将不会选择反对。
因此你（海盗1）可以提出如下方案
你（海盗1）：95个
海盗2:0个
海盗3:1个
海盗4:2个
海盗5:2个
海盗6:0个
分析到这里，就已经结束了，如果又蹦出一个海盗呢？也就是说一共有 7 个海盗呢？
剩下的就交给你了，鉴于篇幅，我就不继续分析了。
最后
今天这道题也是我花了整整一个上午写的，希望能够让你有所收获，或者能够可以给给解解闷，我们下期再见！
老铁们，要不关注一下我，点个赞再走可好？么么哒
