海岛寻宝问题

海岛寻宝问题

  5个人去一个海岛寻宝,最后一共找到了100枚金币。他们约定了一个分配方案,如下:五个海盗按照抽签的顺序依次提出方案,某一个人提出方案之后,剩余存活的人投票表决:方案需要获得超过半数人的认可之后才能被通过,否则方案提出者将会被扔进大海喂鲨鱼,某一个方案被通过后游戏就结束。注:每个人的投票都是在追求自己利益的最大化:保证自己不会被喂鲨鱼的前提下,尽量使自己分到更多的金币。

题意解读

  我们先来理解一下题目意思,如题说的五个海盗按照抽签顺序依次提出方案,所以这是有顺序的,然后半数以上的人认可才能被通过,否则人就没了,比如剩下两个海盗了,那么前面那个海盗就肯定挂了,因为最后那位海盗肯定会投票给自己,只要前面那人挂了他就可以独吞金币。为了解题我们可以先假设一个顺序出来,然后再分析分析怎么make more money

解题思考

  我们先给五个海盗按照顺序编个号分别是A、B、C、D、E,在这个游戏中咱们的每个海盗都要考虑两点make more money活着(注意,这个词我划重点了),刚才我们说到,当只剩俩人时,即只剩D、E时,D肯定就挂了,所以机智的D肯定不能让自己陷入只剩俩人的尴尬处境中。

  考虑到这一点是不是有点思路了,我们应该逆向来推这个问题,从两个人的情况开始模拟;

  • 剩余D、E
    • D必然被投死,收获金币0
    • E收获金币100
  • 剩余C、D、E
    • C需要两票且C知道D不会让自己陷入两人困境肯定会支持自己,再加上自己的票共2票超过了半数,于是大胆的做出了100、0、0的分配
    • D收获金币0
    • E收获金币0
  • 剩余B、C、D、E
    • B需要三票且B知道自己死后D、E都收不到一个金币,于是它可以花1个金币把这俩人收买了让他们投自己,再加上自己的票共3票超过了半数,于是做出了98、0、1、1的分配
    • C收获金币0
    • D收获金币1
    • E收获金币1
  • 兄弟全在A、B、C、D、E
    • A需要三票且A知道自己死后C收不到一个金币,所以可以花1个金币收买了C,还差一票可以在D、E中选一个花2个金币收买让其给自己投票,再加上自己的票共3票超过了半数,于是可以做出97、0、1、2、0或者97、0、1、0、2的分配
    • B收获金币0
    • C收获金币1
    • D/E收获金币2

  所以题目的答案是,在第一个位置的人最有利,最多能够分到最多97个金币🙆♂


评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×