2009 年 11 月 22 日 [京港台]

2009年06月13日 4:23 下午

5个海盗和100块金币的分配问题

鱼儿前天贴了一批Google面试题,最后一道是经典的“海盗分金币”的对弈问题。原题如下:

有5个海盗,按照等级从5到1排列。最大的海盗有权提议他们如何分享100枚金币。但其他人要对此表决,如果多数反对,那他就会被杀死。他应该提出怎样的方案,既让自己拿到尽可能多的金币又不会被杀死?(提示:有一个海盗能拿到98%的金币)

我的解法基于以下的假定:

- 提议者也参与投票;

- “多数”即超过半数;在1-1,2-2的情况下,反对票未超过半数,提议就算通过。

我们来由简到繁地解这道题:

- 在只剩2个海盗(#4,#5)的情形下,#4无论怎样提议都能通过,因为他自己一票就够了,所以他可以拿走全部100枚金币。因为这个结果对#5最不利,所以如果他能得到1枚金币,就会阻止这样的情形出现;

- 也就是说当只剩3个海盗(#3,#4,#5)的时候,#3只要提议给#5分1枚,自己拿99枚,其提议就会通过。这个结果对#4最不利,所以如果他能得到1枚金币,就会阻止这样的情形出现;

- 也就是说当只剩4个海盗(#2,#3,#4,#5)的时候,#2只要提议给#4分1枚,自己拿99枚,其提议就会通过(#2,#4的两票赞成 vs #3,#5两票反对)。这个结果对#3,#5最不利,所以只要他们每个人能得到1枚金币,就会阻止这样的情形出现。

- 于是#1的难题就解决了,他可以提议自己拿98枚,余下两枚分给#3,#5一人一块,#2,#4空手,他的提议就有3票赞成可以通过。

Popularity: 1%

这篇文章归类于: 健康·科技·教育。 (已被阅读 478 次)

37 条评论 发表在“5个海盗和100块金币的分配问题”上
  • 无忌之言 说:

    还真有人不依不挠把此题做成哥德巴赫猜想的?
    Google要是指望来面试的人都需要用人脑做复杂的“递归”(其实更像Fortran的goto语句),那也太无聊了。
    此题应该是在保存自己性命的情况下利益的最大化。
    只关注利益最大化的解法都忽略了“如果多数反对,那他就会被杀死”这一性命攸关的主要矛盾。
    注意是“被杀死”而不仅仅是“出局”!!每个提议的海盗都有个生死的槛要过。
    #5因为不可能死而处在最强势的位子上,把他当成弱势是彻底忽略主要矛盾的结果。
    #4最应该怕死。
    #3因1-1的平衡而渔翁得利,也不太需要怕死。
    #2也是很容易被#3和#5搞死的。
    #1因2-2的平衡又渔翁得利了。

    此题很elegant,也包含了简单的递归,是面试的好题目。
    但如果把生死的因素去掉,则会变得很繁琐,决不适合做一般的面试题。
    复杂的递归是留给愚笨而又勤快的电脑做的。

    这是我最后一次在此发言。

  • 支持中国共产党就是爱中国 说:

    Clause 6: However, for construction 99:0:1 as mentioned as B in my previous post, it should be regarded as an ultra stable solution since the person who can overturn it (#5) has no chance at all to bit on precedent’s imperfect move.

    Clause 7: So far, I can make a conclusion for a perfect world. The best solution is Clause E in my previous post, though the Clause 2 would be preferred, theoretically.

    Clause 8: For imperfect world… we actually do not deal with the imperfect world. We made the scope it is a random system.

    Clause 9: To generalized it: for n bandits, the n0 should offer total number of INT((n-1)/2) coins to others who are not n1, one each, can be randomly.

  • 支持中国共产党就是爱中国 说:

    Clause 3: It solution does contradict to other two stable constructions: 98:0:1:0:1 and 98:0:1:1:0 which indeed was #3 took the last critical position instead of #4. Look at these two constructions closely, I found there is an instable factor associates with them. For one which is not last and is offered with 1 coin, if he finds there is anyone who behind him is not offered the 1, he will find he indeed can make an overturn to reshuffle the history. I am talking about #3 here. By doing so, he indeed is taking a gamble by assume next one to make offer (#2) may make an imperfect move.

    Clause 4: The same is true for #4 in Clause 2.

    Clause 5: The same is true for construction 99:0:1:0, as stated in my previous post, marked with C.

  • 支持中国共产党就是爱中国 说:

    I would like to revise my solution.

    Clause 1: For last one, in this case is #5, if there is anything other than zero, he will accept it, since he is the weakest link and could not act alone to make effect. So the issue can be generalized into a simple Boolean decision making process. From viewpoint of the person who makes the offer, it is not a Boolean decision. It turns out the offer can be and should be rationally either 1 coin or nil coin.

    Clause 2: Recursively applying this conclusion, it would be true too for next last one, which is #4, #3 etc. However, #3 is no longer needed. So the perfect solution should be 98:0:0:1:1.

  • 不平則鳴 说:

    哈!#1就是中国0.4%的人拥有70%的财富。#2就是海外反共分子。#3是民工,#4是國內異義人士,#5是農民。

  • 支持中国共产党就是爱中国 说:

    在不平則鳴的鼓动下,难道我们就此进入了quantum system?太不能解释这种巧合了。

  • 支持中国共产党就是爱中国 说:

    老实讲,random system 和 chaotic system 产生的结论如此接近实在出乎我的意料。当然 random system 并不是一个真实的 random system,chaotic system 更是我胡诌出来的。但结论如此接近实在是。。。太巧合了。

    让我想起一件事:用消灭竞争者以达到最大可能扩散DNA的数学模型来推算 Elizabeth I 的宫廷争斗,居然与真实历史完全吻合,暗示着人类发展可能符合最佳方式。

  • 支持中国共产党就是爱中国 说:

    我说过我没有能力在random system中解这个题。不过老蝎子博看来很不喜欢chaotic system。为尊重博主,我试着在random system中解一下。

    A。我同意老蝎子博的基本思路,那就是先看人数最少的状态。人数最少的状态是一人#5,但因为会议主席一人算1.5票,所以有意义的人数最少的状态是俩人#4和#5。100:0是稳定结构但#5会尽一切可能让人数最少的状态控制在三人,#3#4#5。也就是说100:0是稳定结构但永远不会出现。

    B。三人状态99:0:1是唯一稳定结构,而且无人破坏也破坏不了。一旦进入三人状态,这结构的出现是必然。

    C。四人状态有两个稳定结构:99:0:1:0和99:0:0:1。也就是说上面讲的B永远不会出现。这两个稳定结构出现的概率是相同的。

    D。五人状态有三个稳定结构:98:0:1:0:1和98:0:0:1:1以及98:0:1:1:0。也就是说上面讲的C永远不会出现。

    E。结论:#1自己拿98,剩下的两枚一个一枚,但不分给#2,就可以了。倒霉的#2。

    理性世界与非理性世界差别不是太大。理性世界没有非理性世界那么残酷,草民的利益也只有有限度的保护,当然好过非理性世界。所以,如果代价太大硬搞民运意义也不大。当然,裂变这种变态的人还是一定会搞的。

  • 不平則鳴 说:

    甚麼是quantum system?random system?chaotic system?我看你自己也不懂。難怪被丁小明痛罵,雖然他也是不學無術之輩。

    支持中国共产党就是爱中国的评论
    June 14th, 2009 at 11:25 am
    我没有能力在random system中解这个题。我可以试着在chaotic system 中解一下题。

    既然是 complex system,我就必须将视野扩大到文化范围。要想解好这个题,首要条件是要熟悉海盗文化,就如同海外民运不可能领导中国民运一样。碰巧,这是我的强项。废话少说,我的解答如下:

    我会面对着#5,深情地说给大家听:你还记得你是怎么当上海盗的吗?你因为没有技能找不到好工作,收入是全村最低的。那些村里的有钱人把握着生产资源,设立社会等级,剥削和欺压你这样的穷人,你还记得吗?现在,我们就要分这些金币,按说我是#1,你是#5,我应该多分过你。但我也是穷人出身,我和你一样痛恨等级制度。你说我们是不是应该彻底地消除等级制度?

    然后我面对#4,语调理性地说:你排名倒数第二。如果我们按等级制度分金币,你想一想你能分多少?

    最后我面对大家,激昂地说:我现在提议,让我们彻底消除等级制度共同拥有这些金币吧!想一想,这就等同于你拥有全部的金币。我们誓必拥有全部的金币!让我们团结一至,反对#2企图利用等级制度多分金币的阴谋!现在开始表决,让我们把反对者丢进大海!

  • 老蝎子 说:

    我自觉思想水平与支共总书记的殷切希望还是相差得太远,这辈子恐怕都不可能真正认识理解总书记各项指示的深刻内涵。还是让我和无忌之。言继续打烂仗吧。

    我还不能理解的是,既然我们都知道,如果#1和#2都被干掉,#3将可以拿走99枚金牌,留给#4一枚,而#5将空手而归,那么为什么#5就不明白这个道理,而一定坚持要拿100枚呢?难道是因为他是个榆木脑袋,所以才在海盗团伙里垫底?

    如果#5明白这个道理,那么他有什么理由反对#2给他1枚金币的提议,而要为#3作嫁衣并把自己搞得两手空空呢?

    看不到这一节的人,大概是不熟悉“递归”的概念。但递归是计算机专业最基本的基本功之一。没有这个基本功,还到Google去面试干吗?当然这话也不对,Google里并不是所有的职位都是编程。But you got the idea.

  • 支持中国共产党就是爱中国 说:

    海岛人民共和国。这个名字怎么样?金币管理委员会还是要设的,可以改名叫海岛人民银行,行长暂时空缺。

  • 支持中国共产党就是爱中国 说:

    老蝎子博真是识时务的俊杰。

    要搞革命,搞群众运动,一定要从基层做起。越草根革命性越强,所以#5是第一动员对象。不要看邓玉娇们现在对我们深仇大恨似的,一旦我们与美军开战,她们是最爱国的。所以,民运分子们以为在关键时刻邓玉娇们会反对我们,那是在做青天美梦。

    如果有了#5和#4的支持,革命已经成功了。中间层都是墙头草;#3就是像裂变一样,是标准投机分子。一旦大势已去,#3就会变成革命对象。所以他一定最早表态,会成为比#5还要革命的人。跟何况#2死了,他就是#2了。

    #2对#1来讲当然是最大威胁。所以,就是没这100金币,#2迟早也是要死的。中国人最优良的传统是服从权威。对草跟#4和#5来讲,当他们必须在#1和#2之间选择,自然地,他们会选择支持#1,更何况是#1首先发难,占领了道德的优势。

    所以,这100金币收为国有肯定没有问题。#2到死大概最多只能喊出几句:“#1,我对你衷心耿耿,啊。。。”不是被#5就是#3从背后捅了一刀。如果#4是个人才,这一刀会是他干的。

    #3会不会当金币管理委员会的委员长呢?肯定不会。金币好是好,但他不敢。原来的#2只是听说要分金币就闹到死无葬身之地,新的#2还敢管金币?

    最后,金币归集体管理。可能有人会问,那#1最后不也没得到金币吗?我的回答是,为什么要得到金币呢?我们是实行民主集中制的集体领导模式,样样事都是通过表决这个民主形式作出决定的,#1为什么非要个人得到金币呢?

  • 老蝎子 说:

    坚决拥护支共总书记的无产阶级革命路线!
    让我们紧密团结在#1周围,愤怒声讨叛徒工贼内奸#2的修正主义反革命阴谋!打碎#2的狗头!

  • 阿妞不牛 说:

    最佳解答之一。可以担任谷歌党委书记了。(当然,俺只有赞成权,没有选举推荐权)

    支持中国共产党就是爱中国的评论
    June 14th, 2009 at 11:25 am

    我没有能力在random system中解这个题。我可以试着在chaotic system 中解一下题。

    既然是 complex system,我就必须将视野扩大到文化范围。要想解好这个题,首要条件是要熟悉海盗文化,就如同海外民运不可能领导中国民运一样。碰巧,这是我的强项。废话少说,我的解答如下:

    我会面对着#5,深情地说给大家听:你还记得你是怎么当上海盗的吗?你因为没有技能找不到好工作,收入是全村最低的。那些村里的有钱人把握着生产资源,设立社会等级,剥削和欺压你这样的穷人,你还记得吗?现在,我们就要分这些金币,按说我是#1,你是#5,我应该多分过你。但我也是穷人出身,我和你一样痛恨等级制度。你说我们是不是应该彻底地消除等级制度?

    然后我面对#4,语调理性地说:你排名倒数第二。如果我们按等级制度分金币,你想一想你能分多少?

    最后我面对大家,激昂地说:我现在提议,让我们彻底消除等级制度共同拥有这些金币吧!想一想,这就等同于你拥有全部的金币。我们誓必拥有全部的金币!让我们团结一至,反对#2企图利用等级制度多分金币的阴谋!现在开始表决,让我们把反对者丢进大海!

  • 支持中国共产党就是爱中国 说:

    丁小明博,你把我骂得狗血喷头。现在我想听一听你的解答。

    丁小明的评论
    June 14th, 2009 at 10:40 am
    你是学文的?错了!你是学舔娼妇屁股的,日以继夜,不已乐乎

  • 无忌之言 说:

    >> 只看到#3得99块的可能,没有考虑到没有了#1,他会得0;同理#5也是一样。

    在自己没有生命危险的情况下威胁对方才有真正的威慑力。
    #5没有任何生命危险(!!);
    #4的境况很惨,后面的#5一个人就可以代表多数;
    #3因为#4的境况而很安全;
    #2其实很危险,#3和#5都可以在不影响自己的安全的情况下威胁#2,所以#2最好的办法是提议100块金元都归#3;
    认为#2可以反过来威胁(少得一两块金元)#3或#5是典型的本末倒置!

    抓住主要矛盾,此题其实很容易。

  • 支持中国共产党就是爱中国 说:

    老蝎子,不必与丁晓明计较。我可以理解他。作为一个被统治阶级的成员,疯狂对着统治阶级谩骂,是可以理解的。

    老蝎子的评论
    June 14th, 2009 at 10:51 am
    丁晓明博,我对您老一向敬仰有加。但您对“支共”的攻击越线了,恭请删改。

  • 支持中国共产党就是爱中国 说:

    表决的情况多半是这样的。#3抢着说:我坚决拥护这个提议,让我们把#2绑起来丢进大海!

    我那时一定会说:既然大家都这么说,我听大家的!不过,为了体现我们的人权精神,为了减轻#2在大海中的痛苦,我建议先处死#2,再丢进大海。我还建议我们成立金币管理委员会,由#3任委员长,管理我们的金币。

    大家猜一猜,#3会不会担任金币管理委员会的委员长?

  • 支持中国共产党就是爱中国 说:

    我没有能力在random system中解这个题。我可以试着在chaotic system 中解一下题。

    既然是 complex system,我就必须将视野扩大到文化范围。要想解好这个题,首要条件是要熟悉海盗文化,就如同海外民运不可能领导中国民运一样。碰巧,这是我的强项。废话少说,我的解答如下:

    我会面对着#5,深情地说给大家听:你还记得你是怎么当上海盗的吗?你因为没有技能找不到好工作,收入是全村最低的。那些村里的有钱人把握着生产资源,设立社会等级,剥削和欺压你这样的穷人,你还记得吗?现在,我们就要分这些金币,按说我是#1,你是#5,我应该多分过你。但我也是穷人出身,我和你一样痛恨等级制度。你说我们是不是应该彻底地消除等级制度?

    然后我面对#4,语调理性地说:你排名倒数第二。如果我们按等级制度分金币,你想一想你能分多少?

    最后我面对大家,激昂地说:我现在提议,让我们彻底消除等级制度共同拥有这些金币吧!想一想,这就等同于你拥有全部的金币。我们誓必拥有全部的金币!让我们团结一至,反对#2企图利用等级制度多分金币的阴谋!现在开始表决,让我们把反对者丢进大海!

  • 老蝎子 说:

    丁晓明博,我对您老一向敬仰有加。但您对“支共”的攻击越线了,恭请删改。
    其实“支共”是玩冷幽默的,对他的话不要只看字面。

  • 支持中国共产党就是爱中国 说:

    丁小明,我没说我是学文的。看一下我的解题,我像学文的吗?

    丁小明的评论
    June 14th, 2009 at 10:40 am
    你是学文的?错了!你是学舔娼妇屁股的,日以继夜,不已乐乎

  • 老蝎子 说:

    反正是周末,继续陪大家玩脑力体操。

    >>田方的评论
    >>… 独吞98%的海盜头,不管多精明,多么会算計,到头來只有被小海盜们联手拋入海里鍡鯊鱼。

    不错,这一点我在给鱼儿的跟贴里已经提到。但如果大海盗是萨达姆,无论他提什么样的建议,都会得100%的赞同票。^_^

    >>西雅图一年之中,有兩百八十多个雨天,除非是非常特殊的情况,否則誰需要清洗窗子?

    这是假定应试者熟悉西雅图的气候。Isn’t that a bit presumptuous? 如果面试者是个有着爱因斯坦脑瓜的新移民,但只在终年阳光明媚的硅谷上过两年学,并不清楚西雅图整天以泪洗面的气候特点,岂不也要在这道题上栽了?所以这样的试题其实反映的是Google人的小聪明。

    >> 无忌之言的评论
    >> … 结论和论据已经交叉打结了。
    >> 看来老蝎子博已将“如何将利益最大化”的原题演变成了“看谁更不怕死”的心理战题目了。我已无法奉陪。

    两点不懂:
    1) “结论和论据已经交叉打结了” — 什么意思?哪里打结了?
    2) 至于说“心理战题目”,这本来就是心理战,#1不揣测其余4人的心理,又怎么会得出无须给#2、#4金币的推论?

    这个问题是“囚徒困境”问题的扩展,需要用递归的方法来推算,从最简单的case向上推。我的感觉是无忌之言递归得不彻底。只看到#3得99块的可能,没有考虑到没有了#1,他会得0;同理#5也是一样。

    说来也巧,我刚刚谢绝了一个Google的面试机会,原因我在给鱼的跟贴里也提到了。这些脑筋急转弯或死钻牛角尖的问题只考技巧,对于一个作软件的veteran来讲没有什么意义。

    >> 支持中国共产党就是爱中国的评论

    支共的评论高瞻远瞩,看得我眼花缭乱,甘拜下风。LOL

  • 支持中国共产党就是爱中国 说:

    再看一下Google的题目。让我们先来看一下scope。如果将scope确定为random system,那不能假设海盗们具备这种理性。我的这个断论是建立在观察基础上的:他们是海盗;如果他们具备这种理性,他们不会当海盗;至少他们可以去当研究助理。如果将scope确定为chaotic system,那解题的基点必须适用于complex system,简单化的理性分析就必须被抛弃。我本人水平有限,看不出有可能将scope确定为quantum system。如果多维有高人可以将这个题目的scope确定为quantum system,我一定五体投地。

    所以,我基本可以确定,有一个海盗能拿到98%的金币的提示是忽悠。

  • 丁小明 说:

    尊重博主
    支持中国共产党就是爱中国的评论
    June 14th, 2009 at 10:25 am

    老蝎子看来是学理工科出身的。学理工科出身的出身的人习惯于将 complex system 非 dynamical化。学文科的人可能智商并不高

  • 支持中国共产党就是爱中国 说:

    老蝎子看来是学理工科出身的。学理工科出身的出身的人习惯于将 complex system 非 dynamical化。学文科的人可能智商并不高,但他们对 complex system 的处理能力明显强过理工科出身的,经管 chaos theory 是自然科学的一部分。所以,请不要小看我们共产党。

    举例来说,老蝎子的理性逻辑假设的核心部分是#2会重蹈复辙。事实上,邓小平上台后没有走毛路线,江上台后也没有走邓路线。自限性的出现,本身是dynamical system的一种最终结果,但不必是唯一的结果。多维大部分反共人士的诅咒都是基于一种假设,以为生物自限性是必然结果。哲学上讲,我同意这种假设。现实中,罗马帝国跨越了一千年。中国现在是一个相当稳定的dynamical system,所以,邓玉娇们多变不会对最终结局有任何影响。蜜蜂博是错的;并不是每次蝴蝶煽动翅膀都会引起大洋彼岸的风暴。

  • 支持中国共产党就是爱中国 说:

    老蝎子的解法有问题。老蝎子的解法是假设海盗们都是极具理性的人,他们可以冷静的推断事务发展。老蝎子假设#3,#5是高瞻远瞩大政治家,他们可以理性地推断出,如果自己投了反对票,#1就会被干掉,然后#2又会走#1的老路,然后自己又扮演高瞻远瞩大政治家,又把#2干掉。以此发展,最终自己不利。

    老蝎子解法中的这个理性逻辑假设,在生物学中叫“自限性”,就是当物种发展到一定状况,打破了平衡,对赖以生存的环境或宿主(host)造成了破坏,最终危及到了自己的生存。

    但在同时,老蝎子解法中逻辑假设并不符合他自己设定的假设:“理性”。如果真的海盗们是那么理性的话,#2一定不会走#1的老路。于是,蝴蝶效应(butterfly effect)中的自我干扰现象出现。于是理性假设的最终结果不会出现。老蝎子的解法明显犯了一个错误,将一个 chaotic system 误认为了random system。

  • 无忌之言 说:

    >> “同理#3也不会always vote ‘no’ for less than 99,因为如果干掉#1,#2可以用2枚金牌买通#4和#5,#3一枚也拿不到。”

    结论和论据已经交叉打结了。

    看来老蝎子博已将“如何将利益最大化”的原题演变成了“看谁更不怕死”的心理战题目了。我已无法奉陪。

    >> 如果你是公司主管,而为98%搜尽枯腸,用尽脑汁,你的下場是:“you are fired!”

    海盗贪婪是本分,田方博可能说过了头,其实大公司不同类型的人才都需要,会精算,善于推理,和善于大脑急转弯的人都各有其长处。象老蝎子博这么执着的Google可能也会需要,也许会派他去和微软打交道? :-)

  • 阿妞不牛 说:

    哈哈!

    逻辑推理与推翻逻辑,常规思维与逆向思维,大家都是高手!

    出题的是搞手。

  • 田方 说:

    又如:鱼翔浅底帖中笫3道題:

    “讓你清洗西雅图所有窗子,你收多少費用?”

    西雅图一年之中,有兩百八十多个雨天,除非是非常特殊的情况,否則誰需要清洗窗子?

    如果你去google应徵,又花九牛二虎之力計算洗窗費用,你不会被錄取,理由不是太笨,就是沒常識。公司怎么願意顧用笨人呢?

  • 田方 说:

    恕我直言,遵从问題的設計,規規矩矩地寻求答案,其实都上当啦。

    須知:Google是一家商业公司。現代企业的生存法則,是利润与員工分享。員工受到鼓励,为公司謀取更大利润。

    独吞98%的海盜头,不管多精明,多么会算計,到头來只有被小海盜们联手拋入海里鍡鯊鱼。所以這种小聪明,与公司管理学格格不入。

    如果你是公司主管,而为98%搜尽枯腸,用尽脑汁,你的下場是:“you are fired!”

    如果你到google应徵,遇此问題,你用心算、用筆紙算、十根指头湊着算,你的下場是:連公司大门也休想進去。

  • 老蝎子 说:

    无忌之言的评论
    June 11th, 2009 at 2:18 pm
    1) #3 will always vote ‘no’ for less than 99, and could vote either way for 99
    2) #5 will always vote ‘no’ for less than 100

    这两个结论我不能同意。比如#5,在只剩3人时,他会一枚都拿不到,所以在剩4个人的时候,只要#2分给他1枚,他就应该投赞成票;否则干掉了#2,金牌全归#3。

    同理#3也不会always vote ‘no’ for less than 99,因为如果干掉#1,#2可以用2枚金牌买通#4和#5,#3一枚也拿不到。

  • 老蝎子 说:

    >>但其他人要对此表决

    啊!看题不仔细。想当然认为所有人一起表决,所以从根上错了。谢谢指正。

    如果是所有人一起表决,我的方案就说得通。但按照原题里“但其他人要对此表决”的条件,应该是
    97, 0, 1, 0,2; 或97,0,1,2,0。推理如下:

    - 如果只剩#4,#5,#4就基本上死定了,不论他提什么方案都可能被#5否定,即使他提议所有100枚都归#5,也有死的可能。当然#5也可能饶他一命,但不保险。

    - 所以#4一定要保#3活命,也就是说,如果只剩3人时,无论#3提什么方案#4都会接受,那么#3可以独吞100枚,#4也会投赞成票。尽管#5会投反对票,但1-1,#3的提案还是可以通过。

    - 所以在剩4人时,#2只要分给#4和#5每人一枚金币,他们的结果就一定比只剩3人时要好,所以#2、的提案一定会通过,即98,0,1,1。

    - 所以#1的提案要给#3,#4,#5中两人带来更大的好处,才能保证他们一定会投赞成票。(#2无论如何会投反对票。)

    所以最终#1提议或是97,0,1,2,0或97,0,1,0,2。看不出有什么办法确保能拿到98枚。

  • 无忌之言 说:

    >> 上面是我和“无忌之言”两天前的争论。

    >> “无忌之言”最后那一句“You shouldn’t assume anything not explicitly mentioned. ”是自相矛盾了,因为他作了和我相反的assumption。

    >> If I shouldn’t do it, he should not have done it either. 如果他不assume anything,他就无法答题。

    >> It’s fine to make assumptions, just make sure to be consistent and better follow common sense.

    I call it interpretation (of conditions explicitly said), you call it assumption. But let’s not get too hung up on that.

    原文说“但其他人要对此表决”的“其他”意思很明确,再说你的答案和你的假设完全矛盾!

    You seem to have a big pride. Probably need to cool down a little.

  • 无忌之言 说:

    >> “- 在只剩2个海盗(#4,#5)的情形下,#4无论怎样提议都能通过,因为他自己一票就够了,所以他可以拿走全部100枚金币。因为这个结果对#5最不利,所以如果他能得到1枚金币,就会阻止这样的情形出现;

    >> – 也就是说当只剩3个海盗(#3,#4,#5)的时候,#3只要提议给#5分1枚,自己拿99枚,其提议就会通过。这个结果对#4最不利,所以如果他能得到1枚金币,就会阻止这样的情形出现;

    >> – 也就是说当只剩4个海盗(#2,#3,#4,#5)的时候,#2只要提议给#4分1枚,自己拿99枚,其提议就会通过(#2,#4的两票赞成 vs #3,#5两票反对)。这个结果对#3,#5最不利,所以只要他们每个人能得到1枚金币,就会阻止这样的情形出现。”

    你都证明了#2#3#4都会很贪心,然后又说

    >> “于是#1的难题就解决了,他可以提议自己拿98枚,余下两枚分给#3,#5一人一块,#2,#4空手,他的提议就有3票赞成可以通过。”

    可#3怎可能投赞成票呢?#2#3#4都投反对票#1不是死定了吗?

    你是怎么搞的?不至于吧?!

  • 老蝎子 说:

    上面是我和“无忌之言”两天前的争论。

    “无忌之言”最后那一句“You shouldn’t assume anything not explicitly mentioned. ”是自相矛盾了,因为他作了和我相反的assumption。

    If I shouldn’t do it, he should not have done it either. 如果他不assume anything,他就无法答题。

    It’s fine to make assumptions, just make sure to be consistent and better follow common sense.

  • 老蝎子 说:

    老蝎子的评论
    June 11th, 2009 at 2:12 pm
    I think we have different assumptions:
    - I assume the person who proposes the scheme can also vote;
    - You assume not.

    It’s not clear from the original text, but I think my assumption makes more sense.

    无忌之言的评论
    June 11th, 2009 at 2:18 pm
    1) #3 will always vote ‘no’ for less than 99, and could vote either way for 99
    2) #5 will always vote ‘no’ for less than 100
    3) #2 have to give self 0 to avoid certain death, or 1 to be a toss.
    4) #4 have to give self 0 to avoid certain death.
    5) #1 can easily buy #2 and #4 with 1, no point of give #3 and #5 any

    >> “I assume the person who proposes the scheme can also vote;”
    You shouldn’t assume anything not explicitly mentioned.

  • 老蝎子 说:

    无忌之言的评论
    June 11th, 2009 at 1:58 pm
    Should be 98, 1, 0, 1, 0

    1) When it’s #2 and #4’s term, they have to assign themselves 0, otherwise they will die for sure.
    2) #1 should buy #2 and #4 with 1, otherwise they could vote ‘no’ and then assign themselves 0
    3) #3 and #5 will always vote no, so not point of giving them any.

天蝎

浏览人次: 76837

[作者简介] 从前的天蝎,现在的老蝎

[天蝎]个人类别
作者[天蝎]自己发表的最新评论

2009年十一月
星期一 星期二 星期三 星期四 星期五 星期六 星期天
« 十    
 1
2345678
9101112131415
16171819202122
23242526272829
30  

[天蝎]的个人链接
  • 链接表
Copyright 1999-2003 Chinese Media Net, Inc. All Rights Reserved .