有趣的海盗分⾦币问题
最近⼏天看到⼀个挺有趣的博弈相关的趣谈，今天来分享给⼤家，并且也会详细讲解最终问题的最优解，并且我还好通过这道题扯⼀扯递归。
问题描述
有 5 个海盗，获得了 100 枚⾦币，于是他们要商量⼀个⽅法来分配⾦币。商议⽅式如下：
由 5 个海盗轮流提出分配⽅案，规则如下
糟鱼1、如果超过半数海盗（包括提出者）同意该⽅案，则按照该⽅案分配。
2、如果同意该⽅案的⼈数（包括提出者）⼩于等于半数，则提出者要被扔到海⾥喂鱼，剩下的海盗继续商议分配。
3、海盗们都是绝对理性的，以⾃⼰尽可能多获得⾦币为⽬的。但是在收益相等的情况下，会倾向把提出者扔到海⾥。
表达思念的句子问：第⼀个海盗应该提出怎样的分配⽅案，才能保证⾃⼰既不被扔到海⾥，⼜能使⾃⼰利益最⼤化？
解决问题
先做⼀些假设和提醒
为了⽅便后⾯描述，我们假设轮流提出⽅案的顺序为：海盗5，海盗4，海盗3，海盗2，海盗1；也就是说，最开始由海盗5 提出分配⽅案，海盗1排在最后
并且，⼤家⼀定要注意最后⼀个条件，每个海盗是绝对理性以及在收益相等的情况下，会倾向把提出者扔到海⾥。
大气压是多少前⽅⾼能，开始扯淡，请你发挥出你的各种猜想
好了，现在如果你是海盗5，你会怎么分配才能使得获得的⾦币尽可能多，并且不会被扔进海⾥喂鱼呢？
说实话，第⼀眼看到这个问题，有点⽆从下⼿，脑⼦太特么乱了，因为完全不知道怎么证明我的分配⽅案能够让超过⼀半的海盗都必须⽀持我，要不平均分配？要不我少⼀点他们多⼀点？要不我多⼀点他们少⼀点（这样会不会马上就被扔下海⾥）？
你也可以⾃⼰先想⼏分钟哦，看看你能否⾃⼰想的出来？
事实上，要让别⼈同意我们的想法，我们必须得知彼知⼰，才能百战百胜。也就是说，海盗5要给出分配⽅案，必须基于海盗4的分配⽅案来；也就是说，海盗5得先假设⾃⼰被扔进海⾥的话，海盗4会如何分配呢？然后根据海盗4的分配⽅案，海盗5才能给出他的分配⽅案。
同理，海盗4的分配⽅法得基于海盗3，海盗3得基于海盗2，以此类推
听不懂？没关系，下⾯我举个例⼦你们马上就懂了
逐层击破
1、只有 2 个海盗的情况
现在，我们假设只有两个海盗：海盗1 和海盗2，这个时候你应该知道分配结果了吧？
很显然，⽆论海盗2提出什么⽅案，海盗1 都会直接拒绝，这样海盗1就可能获得全部的⾦币了，也就是说，当只有两个海盗时，海盗2 ⽆论怎么讨好海盗1，最终的结果都是到海⾥喂鱼，所以分配结果如下
2、只有3个海盗的情况
这个时候突然跳出了个海盗3，也参与到这场分赃活动中，这个时候海盗3该如何分配？
其实也⾮常简单，海盗3刚才窥听了海盗1和海盗2的对话，知道如果⾃⼰被扔进海⾥的话，海盗2⼀定也会被扔进海⾥，所以海盗3知道，⾃⼰⽆论提出什么⽅法，海盗2都必须同意，所以海盗3可以提出如下的分配⽅案：
海盗3： 100 个⾦币
海盗2： 0 个⾦币
海盗1： 0 个⾦币。
也就是，只要海盗2⽀持海盗3，就可以形成 2：1的局⾯，海盗3就可以，不需要兼顾海盗1是否⽀持。所以最终的分配结果如下
有⼈可能会说，我们⽤不⽤给海盗2分配⼀点好处？例如分配给海盗2⼀个⾦币，条件3有个规则：在收益相等的情况下，海盗们会倾向把提出者扔到海，答是不需要的，虽然海盗2没有分配到⾦币，但是他并没有被扔进海⾥，这就是最⼤的好处了
看到这⾥，你是不是也知道如果是 4 个海盗或者 5 个海盗，你也会分配了？我相信你⼤概率知道怎么分配了，不过我还是要讲⼀下，因为后⾯随着⼈数的增加，也并没有你想的那么简单，并且后⾯还会和递归算法串讲⼀下。
3、只有4个海盗的情况
这个时候⼜突然蹦出个海盗4，并且海盗4是已经知道了海盗3的分配⽅案了，这个时候海盗4只需要获得其中两个⼈的⽀持即可。
如何获得其中两个⼈的⽀持？
这很容易，拿点钱给海盗1和海盗2就可以了，海盗4可以提出如下分配⽅案
最美女教师海盗4：98个
海盗3：0个
海盗2：1个
海盗1：1个计算机二级考试报名
注意，在收益相等的情况下，海盗们会倾向把提出者扔到海⾥，所以海盗4必须在海盗3的基础上，多给海盗1和海盗2⼀个⾦币，这个时候海盗1和海盗2⼀定会⽀持海盗4，此时的局⾯是 3：1（⽀持：反对的⼈数），因此只有4个⼈的情况下，分配⽅案为：
有⼈可能会问，为啥要拉拢贿赂海盗1和海盗2，咱能不能尝试贿赂下海盗3？
答是咱贿赂不起，如果你有这样的想法，只能说明你不是⼀个合格的海盗！
4、只有5个海盗的情况
如果有5个海盗，其实海盗5和海盗4⼀样，只需要拉拢两个⼈就可以了，那要拉拢谁呢？
这也不难，⾸先必须得贿赂海盗3，给他⼀个⾦币就可以了，其次我们在海盗2或者海盗1之中拉拢⼀个⼈即可，想要拉拢哪⼀个，随你开⼼，所以海盗5可以提出如下⽅案：
网页被篡改怎么办
到这⾥，就已经分配完毕了，是不是觉得很不可思议？原本还怕⾃⼰⽆论提出啥⽅案，都会被扔进海⾥，结果是如此出⼈意料。以后和别⼈分赃，是时候拿出这个规则了
问题的核⼼
我觉得这个问题，⾮常像我们平时学算法中的递归，例如对于递归⽅式：f(n) = f(n - 1) + f(n - 2)，并且给出初始条件 f(1) = f(2) = 1。
那么如果⼀开始要你算 f(n)，你也是⽆从下⼿的，f(n) 必须基于 f(n - 1) 和 f(n - 2)，类⽐于这个海盗问题的话，
1、n 相当于海盗的个数。
2、只有两个海盗时，我们可以⾮常容易着给出⽅案，相当于初始条件 f(1) = f(2) = 1
3、f(n) = f(n - 1) + f(n - 2) 相当于海盗之间定下的规则
所以呢，有时候遇到这种看似很复杂的博弈问题，不妨先从问题的规模尽量⼩处理起，后⾯在逐⼀增加问题的规模。
不妨来个拓展
如果⼜突然冒出了⼀个海盗呢？也就是在⼀共有 6 个海盗的情况下，该如何处理呢？
有没有觉得，从 5 个到 6 个，是⼀个分⽔岭？因为从 5 个开始，就有多种分配⽅案，这个时候就更加考验你的逻辑了。
不过，对于 6 个，我姑且给⼤家分析⼀下，当然，只是我认为是这样，其实我看过别⼈的也有不同的版本。下⾯我来分析下海盗6可以给出的策略：
⾸先，我们必须拉拢 3 个⼈，显然，我们是不可能会拉拢海盗5的，因为咱拉不起。因为我们会从海盗1 ~ 海盗4中考虑。
1、⾸先我们必须拉拢海盗4，因为他最容易贿赂，给他 1 个⾦币即可。
2、接着，我们拉拢海盗3，给他两个⾦币即可
此时，我们已经拉拢了海盗3和海盗4，接下来我们需要在海盗1和海盗2中选⼀个即可，那么问题来了，该给海盗1和海盗2他们多少，他们才愿意同意你的⽅案？
显然，如果我们给海盗1分配 3 个⾦币，海盗2分配 0 个，显然海盗1⼀定会同意。
但是，真的需要给海盗1分配 3 个吗？如果我给他 2 个⾦币，他会同意吗？
答是会的，为什么呢？因为在海盗5的⽅案中，要么是海盗1获得2个，要么是海盗2获得2个，所以对于海盗1来说，海盗5会不会贿赂他，存在不确定性，因此作为⼀个理智的海盗，海盗1是会同意海盗6给他2个⾦币的⽅案的。
因此海盗6可以提出如下⽅案
事实上，也可以从概率上来证明，在海盗5的⽅案中，由于海盗1和海盗2存在不确定性，我们可以进⾏折算，折算成海盗1和海盗2各⾃获得⼀个⾦币，所以我们给他两个⾦币，他必须得同意
当然，如果海盗6要给海盗2分配2个⾦币，然后给海盗1分配 0 个⾦币，也是可以的。**总的来说就是，我们可以从海盗1，海盗2，海盗3中选出两个⼈，然后每⼈给他两个⾦币即可以，这样的组合有三种，因此海盗6可以由如下 3 种⽅案：
分析到这⾥，就已经结束了，如果⼜蹦出⼀个海盗呢？也就是说⼀共有 7 个海盗呢？
剩下的就交给你了，鉴于篇幅，我就不继续分析了。
最后
这么多年以来，今年的春节，估计是最特殊的春节了，想必⼤家都在家⾥呆着，今天这道题也是我花了整整⼀个上午写的，希望能够让你有所收获，或者能够可以给给解解闷，我们下期再见！
⽼铁，要不点个赞再⾛可好？么么哒
1、给俺点个赞呗，可以让更多的⼈看到这篇⽂章，顺便激励下我，嘻嘻。
2、⽼铁们，关注我的原创「帅地玩编程」，专注于写算法 + 计算机基础知识（计算机⽹络+ 操作系统+数据库+Linux）。
保存让你看完有所收获，不信你打我。后台回复『电⼦书』送你⼀份精选电⼦书⼤礼包，包含各类技能的优质电⼦书。
作者简洁
作者：⼤家好，我是帅地，从⼤学、校招⼀路⾛来，深知算法，计算机基础知识的重要性，所以申请了⼀个微星『帅地玩编程』，专业于写这些底层知识，提升我们的内功，帅地期待你的关注，和我⼀起学习。 转载说明：未获得授权，禁⽌转载
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论