当前位置: 代码迷 >> 综合 >> 海盗分赃问题-----简化问题,分而治之
  详细解决方案

海盗分赃问题-----简化问题,分而治之

热度:15   发布时间:2023-12-26 20:56:52.0

目录

问题描述:

问题分析:

问题求解:(简化问题,分而治之)

假设有两个海盗进行分赃:(4号和5号)

假设有三个海盗进行分赃:(3号、4号和5号)

假设有四个海盗进行分赃:(2号、3号、4号和5号)

当有五个海盗进行分赃的时候:(1号、2号、3号、4号和5号)

总结:


问题描述:

        五个极其聪明的海盗抢到100颗宝石,每一颗宝石都一样大小和价值连城。他们决定以抽签投票的方式来分配这些宝石:有(1、2、3、4、5)五个号码,每人抽取一个。首先,由1号提出分配方案,然后大家举手表决,当且仅当超过半数的人同意时,按照他的分配方案 进行分配,否则将被扔进海里喂鲨鱼。如果1号死后,再由2号提出分配方案,规则如前所述,以此类推。

问:第一个海盗提出怎样的分配方案才能使自己的收益最大化?为什么?


问题分析:

  • 每个海盗都及其聪明       ---->       每个海盗都会做出对自己做大利益化的选择
  • 每颗宝石都价值连城       ---->       即使只得到一颗宝石也会成为富翁
  • 当且仅当超过半数人同意时即通过        ----->        必须要赢得半数以上的人支持才行
  • 金钱准则                        ----->       财不外露,越少人知道越好
  • 人性弱点                        ----->       活着总比死了好
  • 此推理模型只在逻辑层面进行推理,不牵扯到深层次的社会工程学问题。

问题求解:(简化问题,分而治之)

对于五个海盗分赃时考虑的情况相对比较复杂,可以先假设只有两或三或四个海盗来按指定的规则来分配。

假设有两个海盗进行分赃:(4号和5号)----(为了与原题内容相互对应,便于理解我们使用4号和5号标签来标识这两个海盗,下同)

由于表决需要半数以上的人支持才能通过,5号又有心让4号被喂鲨鱼,所以无论4号提出什么方案都不能逃脱被喂鲨鱼的命运。

则此种情况下,5号会先杀死4号自己独占100课宝石。

也即:4号(die)    0 颗

           5号           100颗

假设有三个海盗进行分赃:(3号、4号和5号)

如上述分析,若3号被喂鲨鱼,则4号也逃不过被喂鲨鱼的命运,所以无论3号提出什么样的分配方案,4号都会表示支持,且此时3号提出的方案会通过,也就说3号可以独占100颗宝石。此时的表决为2:1,表决通过。

也即:3号           100颗

           4号            0颗

           5号            0颗

假设有四个海盗进行分赃:(2号、3号、4号和5号)

如上所述,若2号被喂鲨鱼,则4号和5号也分不到宝石,所以2号只需向4号和5号施加一点小惠,即可得到最大的收益。也就是说2号给4号和5号各一颗宝石,自己独占剩下的宝石,此时的表决为3:1,表决通过。

也即:2号            98颗

          3号             0颗

          4号             1颗

          5号             1颗

则当有五个海盗进行分赃的时候:(1号、2号、3号、4号和5号)

如上所述,若1号死后,2号可以得到98颗宝石,所以2号不会同意1号的任何方案。

                   若1号死后,由2号进行分配时,3号将得不到宝石,所以建议向3号实惠。

                   若1号死后,由2号进行分配时,4号和5号的被分配到的宝石一样,在此再赢得一票支持,1号就能以3:2的结果得到最大的收益。

也即:1号       97颗

           2号       0颗

           3号       1颗

           4号        2颗

           5号        0颗


总结:

        对于一些比较复杂的问题不容易很快找到答案时,尝试将其划分成一个个很小的模块,但需要保证每一块的整体模式是不变的或相似的,然后从底层开始剖析,直至剖析出问题的答案时,即此题的正解。此种解题的思想被称为“简化问题,分而治之”。