`
seawavenews
  • 浏览: 231558 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
文章分类
社区版块
存档分类
最新评论

海盗分金币

阅读更多

海盗分金币

题目:10名海盗抢得了窖藏的100块金子,并打算瓜分这些战利品。这是一些讲民主的海盗(当然是他们自己特有的民主),他们的习惯是按下面的方式 进行分配:最厉害的一名海盗提出分配方案,然后所有的海盗(包括提出方案者本人)就此方案进行表决。如果50%或更多的海盗赞同此方案,此方案就获得通过 并据此分配战利品。否则提出方案的海盗将被扔到海里,然后下提名最厉害的海盗又重复上述过程。

问:最凶的一名海盗应当提出什么样的分配方案才能使他获得最多的金子呢?

这难题已经流传了至少十年,但是Omohundro对它作了改动,使它的逻辑问题变得分外复杂了。即500名海盗瓜分100块金子。


    数学的逻辑有时会导致看来十分怪异的结论。一般的规则是,如果逻辑推理没有漏洞,那么结论就必定站得住脚,即使它与你的直觉矛盾。 1998年9月,加利福尼亚州帕洛阿尔托的Stephen M. Omohundro寄给我一道难题,它恰好就属于这一类。这难题已经流传了至少十年,但是Omohundro对它作了改动,使它的逻辑问题变得分外复杂 了。
    先来看看此难题原先的形状。10名海盗抢得了窖藏的100块金子,并打算瓜分这些战利品。这是一些讲民主的海盗(当然是他们自己特有的民主),他们的习惯 是按下面的方式进行分配:最厉害的一名海盗提出分配方案,然后所有的海盗(包括提出方案者本人)就此方案进行表决。如果50%或更多的海盗赞同此方案,此 方案就获得通过并据此分配战利品。否则提出方案的海盗将被扔到海里,然后下提名最厉害的海盗又重复上述过程。
    所有的海盗都乐于看到他们的一位同伙被扔进海里,不过,如果让他们选择的话,他们还是宁可得一笔现金。他们当然也不愿意自己被扔到海里。所有的海盗都是有 理性的,而且知道其他的海盗也是有理性的。此外,没有两名海盗是同等厉害的——这些海盗按照完全由上到下的等级排好了座次,并且每个人都清楚自己和其他所 有人的等级。这些金块不能再分,也不允许几名海盗共有金块,因为任何海盗都不相信他的同伙会遵守关于共享金块的安排。这是一伙每人都只为自己打算的海盗。 最凶的一名海盗应当提出什么样的分配方案才能使他获得最多的金子呢?
    为方便起见,我们按照这些海盗的怯懦程度来给他们编号。最怯懦的海盗为1号海盗,次怯懦的海盗为2号海盗,如此类推。这样最厉害的海盗就应当得到最大的编号,而方案的提出就将倒过来从上至下地进行。
    分析所有这类策略游戏的奥妙就在于应当从结尾出发倒推回去。游戏结束时,你容易知道何种决策有利而何种决策不利。确定了这一点后,你就可以把它用到倒数第2次决策上,如此类推。如果从游戏的开头出发进行分析,那是走不了多远的。其原因在于,所有的战略决策都是要确定:"如果我这样做,那么下一个人会怎样做?"
    因此在你以下海盗所做的决定对你来说是重要的,而在你之前的海盗所做的决定并不重要,因为你反正对这些决定也无能为力了。
    记住了这一点,就可以知道我们的出发点应当是游戏进行到只剩两名海盗——即1号和2号——的时候。这时最厉害的海盗是2号,而他的最佳分配方案是一目了然 的:100块金子全归他一人所有,1号海盗什么也得不到。由于他自己肯定为这个方案投赞成票,这样就占了总数的50%,因此方案获得通过。
    现在加上3号海盗。1号海盗知道,如果3号的方案被否决,那么最后将只剩2个海盗,而1号将肯定一无所获——此外,3号也明白1号了解这一形势。因此,只 要3号的分配方案给1号一点甜头使他不至于空手而归,那么不论3号提出什么样的分配方案,1号都将投赞成票。因此3号需要分出尽可能少的一点金子来贿赂1 号海盗,这样就有了下面的分配方案: 3号海盗分得99块金子,2号海盗一无所获,1号海盗得1块金子。
    4号海盗的策略也差不多。他需要有50%的支持票,因此同3号一样也需再找一人做同党。他可以给同党的最低贿赂是1块金子,而他可以用这块金子来收买2号 海盗。因为如果4号被否决而3号得以通过,则2号将一文不名。因此,4号的分配方案应是:99块金子归自己,3号一块也得不到,2号得1块金子,1号也是 一块也得不到。
    5号海盗的策略稍有不同。他需要收买另两名海盗,因此至少得用2块金子来贿赂,才能使自己的方案得到采纳。他的分配方案应该是:98块金子归自己,1块金子给3号,1块金子给1号。
    这一分析过程可以照着上述思路继续进行下去。每个分配方案都是唯一确定的,它可以使提出该方案的海盗获得尽可能多的金子,同时又保证该方案肯定能通过。照 这一模式进行下去,10号海盗提出的方案将是96块金子归他所有,其他编号为偶数的海盗各得1块金子,而编号为奇数的海盗则什么也得不到。这就解决了10 名海盗的分配难题。
    Omohundro的贡献是他把这一问题扩大到有500名海盗的情形,即500名海盗瓜分100块金子。显然,类似的规律依然成立——至少是在一定范围内 成立。事实上,前面所述的规律直到第200号海盗都成立。 200号海盗的方案将是:从1到199号的所有奇数号的海盗都将一无所获,而从2到198号的所有偶数号海盗将各得1块金子,剩下的1块金子归200号海 盗自己所有。
    乍看起来,这一论证方法到200号之后将不再适用了,因为201号拿不出更多的金子来收买其他海盗。但是即使分不到金子,201号至少还希望自己不会被扔进海里,因此他可以这样分配:给1到199号的所有奇数号海盗每人1块金子,自己一块也不要。
    202号海盗同样别无选择,只能一块金子都不要了——他必须把这100块金子全部用来收买100名海盗,而且这100名海盗还必须是那些按照201号方案将一无所获的人。由于这样的海盗有101名,因此202号的方案将不再是唯一的——贿赂方案有101种。
    203号海盗必须获得102张赞成票,但他显然没有足够的金子去收买101名同伙。因此,无论提出什么样的分配方案,他都注定会被扔到海里去喂鱼。不过, 尽管203号命中注定死路一条,但并不是说他在游戏进程中不起任何作用。相反,204号现在知道,203号为了能保住性命,就必须避免由他自己来提出分配 方案这么一种局面,所以无论204号海盗提出什么样的方案,203号都一定会投赞成票。这样204号海盗总算侥幸拣到一条命:他可以得到他自己的1票、 203号的1票、以及另外100名收买的海盗的赞成票,刚好达到保命所需的50%。获得金子的海盗,必属于根据202号方案肯定将一无所获的那101名海 盗之列。
    205号海盗的命运又如何呢?他可没有这样走运了。他不能指望203号和204号支持他的方案,因为如果他们投票反对205号方案,就可以幸灾乐祸地看到 205号被扔到海里去喂鱼,而他们自己的性命却仍然能够保全。这样,无论205号海盗提出什么方案都必死无疑。206号海盗也是如此——他肯定可以得到 205号的支持,但这不足以救他一命。类似地,207号海盗需要104张赞成票——除了他收买的100张赞成票以及他自己的1张赞成票之外,他还需3张赞 成票才能免于一死。他可以获得205号和206号的支持,但还差一张票却是无论如何也弄不到了,因此207号海盗的命运也是下海喂鱼。
    208号又时来运转了。他需要104张赞成票,而205、206、207号都会支持他,加上他自己一票及收买的100票,他得以过关保命。获得他贿赂的必 属于那些根据204号方案肯定将一无所获的人(候选人包括2到200号中所有偶数号的海盗、以及201、203、204号)。
    现在可以看出一条新的、此后将一直有效的规律:那些方案能过关的海盗(他们的分配方案全都是把金子用来收买100名同伙而自己一点都得不到)相隔的距离越 来越远,而在他们之间的海盗则无论提什么样的方案都会被扔进海里——因此为了保命,他们必会投票支持比他们厉害的海盗提出的任何分配方案。得以避免葬身鱼 腹的海盗包括201、202、204、208、216、232、264、328、456号,即其号码等于200加2的某一方幂的海盗。
    现在我们来看看哪些海盗是获得贿赂的幸运儿。分配贿赂的方法是不唯一的,其中一种方法是让201号海盗把贿赂分给1到199号的所有奇数编号的海盗,让 202号分给2到200号的所有偶数编号的海盗,然后是让204号贿赂奇数编号的海盗,208号贿赂偶数编号的海盗,如此类推,也就是轮流贿赂奇数编号和 偶数编号的海盗。
    结论是:当500名海盗运用最优策略来瓜分金子时,头44名海盗必死无疑,而456号海盗则给从1到199号中所有奇数编号的海盗每人分1块金子,问题就 解决了。由于这些海盗所实行的那种民主制度,他们的事情就搞成了最厉害的一批海盗多半都是下海喂鱼,不过有时他们也会觉得自己很幸运——虽然分不到抢来的 金子,但总可以免于一死。只有最怯懦的200名海盗有可能分得一份脏物,而他们之中又只有一半的人能真正得到一块金子,的确是怯懦者继承财富。

 
分享到:
评论

相关推荐

    经典海盗分金C++源码

    经济学上有个“海盗分金”模型,是说5个海盗抢得100枚金币,他们按抽签的顺序依次提方案:首先由1号提出分配方案,然后5人表决,超过半数同意方案才被通过,否则他将被扔入大海喂鲨鱼,依此类推。“海盗分金”其实是...

    海盗分金 python 源码

    #经济学上有个“海盗分金”模型:是说5个海盗抢得100枚金币,他们按抽签的顺序依次提方案:首先由1号提出分配方案,然后5人表决,投票要超过半数同意方案才被通过,否则他将被扔入大海喂鲨鱼,依此类推。 #假定“每...

    海盗分金源代码

    2. 改变一下规则,投票中方案必须得到超过50%的票数(只得到50%票数的方案的提出者也会被丢到海里去喂鱼),那么如何解决5个海盗分100枚金币的问题? 3. 不改变规则,如果让100个海盗分100枚金币,会发生什么? 4. ...

    海盗分金问题C语言解答

    【海盗分金问题】是一个经典的逻辑与算法问题,源自计算机科学中的博弈论。在这个问题中,一群海盗在海上找到了一定数量的黄金,并需要按照特定的规则来分配这些黄金。问题的关键在于,这群海盗遵循两个原则:一是每...

    笔试面试智力试题汇集

    在经典的海盗分金币问题中,五个海盗通过特定的规则来决定如何分配他们共同抢劫来的100枚金币。这个问题不仅考验应试者的逻辑思维能力,还涉及到博弈论中的逆向归纳法。 **题目内容:** 五个海盗通过抽签决定分配...

    akh_0624_应聘笔试智力测验题库(附答案)

    从给定的文件信息中,我们可以提取到两个主要的知识点:一是关于“海盗分金币”的逻辑推理题,二是关于“猜牌问题”的智力测验。接下来,我们将详细解析这两个知识点。 ### 海盗分金币 #### 题目背景与规则 在题目...

    2014年第五届蓝桥杯大赛软件类JAVA-A组全国总决赛真题.doc

    ### 知识点一:海盗分金币问题 #### 问题背景 在2014年第五届蓝桥杯大赛软件类JAVA-A组全国总决赛中,出现了一道名为“海盗分金币”的题目。题目背景设定为五位海盗在一次帆船比赛中遭遇天气突变,各自在途中的一座...

    经典智力题.doc

    海盗分金币问题的描述是:5个海盗抢得100枚金币后,讨论如何进行公正分配。他们商定的分配原则是:(1)抽签确定各人的分配顺序号码(1,2,3,4,5);(2)由抽到1号签的海盗提出分配方案,然后5人进行表决,如果方案...

    各大名企笔试面试智力题附答案汇总

    #### 海盗分金币问题解析 这个问题是经典的博弈论题目,考察的是参与者的逻辑思维能力和对博弈论的理解。题目设定在一个假设的情境下,五个海盗通过抽签决定分配顺序,然后根据特定规则进行金币的分配决策。 **...

    第五届蓝桥杯软件类决赛真题(Java语言A组).pdf

    #### 一、海盗分金币 **题目背景与分析:** 题目描述了五个海盗在一次帆船比赛中遭遇恶劣天气后,相继在一个荒岛上发现了同一堆金币,并各自按照一定规则取走了部分金币。最终,在目的地集合时才发现这一有趣的现象...

    asdf.rar_海盗分金

    【标题】:“asdf.rar_海盗分金”是一个与编程竞赛相关的压缩文件,其中包含了实现“海盗分金”问题的源代码。这个问题源自于算法竞赛,特别是ACM(国际大学生程序设计竞赛)训练中的经典题目。 【描述】:描述中...

    计算机导论作业3(1)-converted1

    - 海盗分金币问题是一个经典的递归逻辑问题,可以通过动态规划解决,确保每个海盗都能存活下来。 - 传教士与土著士兵渡河问题同样涉及逻辑和策略,需要保证在任何时候,传教士的数量都不少于士兵,可以通过多次...

    一些关于笔试智力题很好的

    1. **海盗分金币问题**:这是一个经典的博弈论问题。海盗们需要确保自己在分配金币的过程中存活下来,并尽可能获得更多的金币。关键在于,海盗需要考虑后面的海盗会如何投票以确保自己的方案通过。对于1号海盗来说,...

    微软面试15题

    22. 海盗分金币问题:使用动态规划,可以找出让最高级海盗获得最多金币的分配策略。 23. 组合最小整数:可以使用贪心策略,按升序遍历集合A,每次选择能构成最小整数的下一个数字。 【百度面试题解析】 24. 字符...

    google面试,笔试逻辑题及答案.doc

    17. 海盗分金币:最大的海盗提出方案,使自己利益最大化且不会被投票否决,涉及策略和概率。 这些问题涵盖了逻辑推理、概率统计、问题解决等多个领域,是Google评估潜在员工能力的有效方式。解答这些问题需要清晰的...

    百度面试题大收集算法

    这是一个概率问题,海盗头子分金币使得每袋数量不同。可以通过随机算法生成不同的数字,确保不重复,直到100袋都满。题目中给出的代码使用了静态数组和循环来避免重复,通过不断生成新的随机数并与已分配的数字对比...

    4第四章决策与战略管理.pptx

    在案例中,海盗分金币问题展示了决策的策略性。1号海盗通过理智计算,提出了一个既能保证自身安全又能最大化收益的方案。这个问题揭示了决策中的博弈和逻辑推理。 决策过程包括识别问题、确定目标、拟定可行方案、...

    微软、谷歌、百度等公司经典面试

    第22题是海盗分金币问题,属于博弈论范畴,需要逻辑推理能力。第23题是数字组合问题,需要找到最小的数字组合超过给定值。 8. **语言特性和函数**:第16题要求设计一个生成序列的函数,考察函数定义和数组操作。第...

    google的面试题

    17. **海盗分金币**:最高级的海盗(5号)应该提出方案:100枚金币全给自己,其余每人一枚。4号和3号会投票支持,因为他们知道自己会得到金币,否则5号会死亡,他们将一无所有。 这些问题揭示了Google面试的多样性...

    微软谷歌等各大公司面试题目

    22. **海盗分金币问题**:基于逻辑推理的博弈论问题,可用递归或动态规划解决。 23. **组成大于K的最小整数**:贪心策略,优先使用较大的元素。 24. **字符串倒序**:直接交换字符串的首尾,直到中间位置。 25. *...

Global site tag (gtag.js) - Google Analytics