一些趣题之一:三人分桃汁问题。

暑假里要帮波波出书准备逻辑推理趣题,回到上海就去翻我那堆压箱底的奥数书和趣味数学书去,我从前就数这类书最多,找几十道题目还是容易的。当然,为了原创性,题目和解答我都会重写。

先想到那个五个海盗分赃的问题:5个海盗分共100粒宝石,5人依次提出分配方案,若方案得到活着的半数以上的海盗支持则通过,若不通过则把提出方案的人丢到海里剩下的人继续,所有的人都是足够聪明的,只要不被丢到海里,就会选择最大的利益,问第一位海盗最多能获得多少宝石。这道题中的海盗数可以改成100多个。500个等,情形又会发生变化……

还想到一道趣味思考题,虽然严格说不能算逻辑推理题,但挺有意思:

三人分桃汁:

古代有二桃杀三士的故事,三人分赃确实不容易。以脑筋急转弯的思路,或许有人会说:榨成桃汁不就行了?那确实不错,不过三人分桃汁似乎也不是件容易事……

在没有计量工具的情况下,单凭目测手分,如何能让三个人都感到分配公正?

条件是:三个人都相信自己的切分能力保证是最公正的,但都不信任他人的切分技术。

………………………………………………………………

提示:

先参考“二人分饼”的思路:很简单,甲先把饼分成自认为公平的两份,然后让乙在其中挑选一份,这样双方都会觉得公平。

………………………………………………………………

解答:

甲先分成自以为公平的3份:A、B、C。

然后乙来,对三份重新进行分割。有两种情况:

情形一:乙认为甲的分割有一个大于等于三分之一,另两个都小于等于三分之一。不妨设乙减少A,增加到B、C上。此时被乙改动后的三份记做A-、B+、C+。

然后丙来看,如果丙认为最大的是A-,则丙自己拿A-,剩下两个怎样分给甲、乙,他们都会觉得公平。

如果丙认为最大的是B+或C+,不妨设丙认为最大的是B+,则把C+分给甲,把A-分给乙,即可。

情形二:乙认为甲的分割有一个小于等于三分之一,另两个都大于三分之一。不妨设乙减少A、B,增加到C上。此时被乙改动后的三份记做A-、B-、C+。

然后丙来看,如果丙认为最大的是A-或B-,不妨设丙认为最大的是A-,则丙自己拿A-,把C+分给甲,把B-分给乙,即可。

如果丙认为最大的是C+。则不妨设丙认为最小的是A-。则将A-分给乙。然后以“二人分饼”的方式,把B-、C+两份放一起,再重新分割为丙认为公平的两份,最后让甲选择其中一份。由于A-比甲所认为的三分之一还要小,所以甲认为B-和C+加起来超过三分之二。最后大家都觉得公平。

2006年8月3日

  • 古雴

    2008-12-01 18:48:30 

    你继续把原本不属于我的思路强加于我吧……这有什么意思呢?你说我得出了许多错误结论,但事实上你倒说说我究竟下了哪一个结论过没有?我几乎一个结论都没有下,我给出的唯一一个结论是:问题并不如你原先想的那么简单。仅此而已,其余都是在挑你的错误。我用了什么错误的前提?我只是在说你的前提是不可靠的,是循环论证。
    如果你承认你的论证并不严密,我的目的就达到了;如果你死不承认,我也无话可说。总之我没有更大的野心去解决这个问题。如果你有心想要给出一个完整和严格的论证,那么请不要和我纠缠不清,直接把完整的论证写出来,那么我愿意帮你检查。不然的话,你究竟要和我争什么呢?
    关于你的错误我最后给你提示吧:“5号针对此4个数字的概率表一旦形成,1-4号的选择将仅依赖这个表格”——这没错!但是,概率表中的“>”和“=”是有根本差异的!决不能简略成“>=”来做。某个人的博弈策略即便只增加一点点的偏重,情况就将发生质变。而我之前提议的方案中的关节要害都在于50%-50%的对等情况,岂能用一个>=而把=的情况掩盖掉?
    你或许能找到新的反驳,但我希望你不要把精力都花在和我纠缠不清上面,因为我向来只是挑你的漏洞而没有企图给出独立的证明,这是我反复说反复说了的。你究竟有没有听进去?你究竟有没有承认我从没有给出一个独立完整的方案的意图?你究竟有没有承认你最初的论证是不严密的?
    如果你已经写出了完整而自信无懈可击的论证,你可以整个发给我,然后我会告诉你第几行出了错。或者如果我挑不出错,就一定会承认你确实厉害。如果你拿不出最终的结果,那么请容许我不想再讨论这道题目了。我早就承认这道题超过了我的能力,而且我也没有太高的兴致来玩自我挑战。我想你应该能够允许我缴枪投降吧?能允许我不再试图解决这道问题吧?为什么我必须认同你以后才能放弃?

  • igeli

    2008-12-01 18:01:23 

    我记得你用很长的篇幅来论述5号必须选16,17来给1号增加压力,给自己留下空间,还有关于16,17号是对称的等等…
    我好像没有直接指出过,但你从我的举例中应该能看到,我根本就不认为这是正确的—我以为你慢慢自己就明白了,看起来不是。我的观点是:5号针对此4个数字的概率表一旦形成,1-4号的选择将仅依赖这个表格,和之前的概率推理没有任何关系,那4个数字对5号是等价的,不存在优先选哪个的问题,也不存在对称问题,你在这个问题上大概陷入太深了,所以推论出许多错误结论,你仔细想想,自己的那个前提是不是错误了:)

  • 古雴

    2008-11-30 20:01:58 

    数学这个东西的好处就在于错了就是错了,不得不承认。所以当你提出“三人分桃汁”问题的更好的方案时,我一开始也是认定你错了,但随即我想通了,就承认了自己看错了,你没错。这确实没什么大不了的。
    但和这里没有关系。我早就自己指出我给出的方案是有漏洞的,而且我也指出了我的方案究竟在哪里是不严密的。但你非要用你的一套错误的论证来指明我的错误,这当然是我不能接受的。
    为什么我终止讨论?确实,即便作业繁忙,如果是有意思的问题,我也乐意讨论。所以终止讨论的真正原因是这个讨论已经没意思了。我发现我开始不断地重复我已经提到过的问题,但对你而言都毫无注意,还是反复逼迫我不断地再重复我说过的问题。
    你最后提到的疏忽当然不是我所谓的错误,还需要我重复再重复吗?那我再重复一遍——我说的是“你的论证从一开始犯了一个显而易见的错误”。注意,是“一开始”,不是要等到什么1-a之类的才出现的。所以你这个一般性论证没法帮你完善,因为一开始第一步就不过关——“而且这个问题我也早就提示过多次了”。我都这么写了,你都好像没看到似的,去自说自话地想象说我发现的是这样的小漏洞……所以总而言之我感觉到在后来的讨论中我说的许多话都是说了白说,你都没注意。所以我不说了,再多说,重复来重复去,你又不注意,徒然浪费精力。
    我早就承认,严密地解决这道题目,我无能为力。我做不来!做不来又有什么大不了呢?现实生活中每个人都还会有很多事情做不来呢。一道纸上谈兵的问题解决不了算得了什么?但是如果是因为不愿承认自己没做出而始终不愿意终止讨论,还非得要别人陪着折腾不休,我觉得就不只是解题的能力问题了,而是说明你的心态还不够成熟。

  • igeli

    2008-11-30 19:00:17 

    出去了两天,以为你一定丰富了讨论的内容,没想到,你说讨论中止了。
    也许真的如你说:老师布置了作业;你对数学失去兴趣了…
    或者,还有另外的原因:比如你看到即将得出的结论对你不利…
    其实,凭你的聪明头脑,把我说的那个证明能很容易丰富完善起来,推广到一般情况;或者就指出它不可弥补的致命漏洞。
    我觉得我们的讨论总的气氛不错,虽然中间略有措辞激烈,但一直在围绕解答问题这一主线。说到底,这不就是一道题吗,对了错了有什么大不了,谁不会犯错误呢?现实生活中每个人还会犯错误呢,一道纸上谈兵的题目错误算得了什么?但是如果真的是因为发现自己错误而终止讨论,我觉得就不只是一道题目的对错问题了,而是说明你的心态还不够成熟。清华北大的就不会犯错误了吗?其实意识到自己的错误,并且帮助对手完善他对自己错误的证明,不仅不会让自己掉价,还会让自己受人钦佩,你说是吗?
    但愿我说的后一个理由并不存在,那上面的话也就算没说。
    祝你顺利!

  • 古雴

    2008-11-26 14:53:06 

    你才太犟呢,你怎么就不肯多想一层呢?我已经说过,16和17不是随便的两个数字,第5人只能靠选16或17威胁第一第二人。事实上第五人的威胁只有针对前两人才管用,第五人如果减少选16或17的概率,增加选15或18的概率,就将不会给第一第二人造成逼迫。如果第5人各以30%的概率选择16、17,各以20%的概率选择18或15,那么他就威胁不到第一第二人,因为尽管第一人选16或17将只有80%的存活率,但选15或18的话存活率更低,所以不会受到逼迫而改选。而如果第5人不逼迫前两人,他就没有别的办法。事实上第三、第四人是不会受第五个人逼迫的。因为他们就算知道自己被第五人盯上,他们的存活率也仍旧至少是50%,而如果他们改变策略,存活率反而不如50%,所以第五人不可能通过威胁第三第四人的方式迫使他们让道。关键在于只有第一第二人优势比较大,他们有机会获得远远高于50%的存活率,因此威胁才是有效的。第三第四人的存活率本来就在50%左右,再怎么威胁,由于对称性,威胁的死亡率也一般不回超过50%,所以第三第四人不是威胁的对象。因此第五人的唯一手段就是舍身攻击的威胁,而这一手段唯一可能奏效的对象就是前两人,而这一手段对前两人产生影响的唯一方式是以极大的概率选择16或17——而如果选择1或2等对前两人没有任何威胁。所以聪明的第一个人当然能够知道威胁16和17是第五个人必然采取的唯一手段。你明白了没有?没明白就算了,我也不再说了。
    暂时关闭评论。

    更正:“如果第5人各以30%的概率选择16、17,各以20%的概率选择18或15,那么他就威胁不到第一第二人,因为尽管第一人选16或17将只有80%的存活率,但选15或18的话存活率更低,所以不会受到逼迫而改选。”
    应为“如果第5人各以20%的概率选择16、17,各以30%的概率选择18或15,那么他就威胁不到第一第二人,因为尽管第一人选16或17将只有80%的存活率,但选15或18的话存活率更低(70%),所以不会受到逼迫而改选。”
    而此时第一第二人不会改选而是仍旧选16、17,但第三第四人也不会改选,因为他们照旧选15或18的存活率反而提高到70%,正好高兴,绝不可能给第五人让道。
    所以第五个人有可能威胁到前两个人的策略决不是无限的,事实上是非常少的。必须以极大的概率选择16或17才有威胁,这个概率只要少于某个值,就不会具有威胁。
    所以第五人的策略首先是必须使16或17的概率足够大以至于威胁到前两个人的选择,其次再考虑如何可能让自己活得最大的存活率。这个增加存活率的考虑将进一步筛选出最优的策略。比如说各以50%的概率选择16或17的话能够使自己获得x%的存活率(由于第四个人的微妙,似乎达不到50%)。而如果各以49%的概率选择16或17,以2%的概率选择1,尽管仍足以威胁到前两人,但第五人得到的存活率将决不会比x大,因为额外的选1的可能性对局势没有影响,只是单纯的自杀而已。
    所以根据最终给第五人带来的存活率的高低,我们可以在第五人所有可以威胁到前两人的策略中排个序。其中必有某个策略将带来的存活率是最大的。那么这一条策略就是第五人的最佳策略。这条策略是唯一确定的,任何聪明人都可以算得出来,所以不需要第五人声明,其他聪明人就能够知道第五人必然采取的最佳策略。
    以上!

  • igeli

    2008-11-26 13:45:05 

    问题已经如此清晰,你还没有意识到吗?
    比如按照你的想法,我们可以给5号设定无数最佳策略,它们的结果(按你的推理)都会让5号得到50%的生存机会,例如:5号可以有最佳策略2:分别以50%的概率选15,16,或者最佳策略3,分别以85%,15%的概率选18,15…等等,你凭什么说他一定死抱着16,17而迫1,2号让路呢?
    至于你多次提到博弈原理,逻辑学计算,想必你对这方面很有研究,但现在你哪怕把整个教科书都搬过来,也救不了5号的命,因为真理是越辩越明的:)
    对不起,说话冲了点,觉得你太犟:)

  • 古雴

    2008-11-26 09:09:03

    稍微总结一下:
    Igeli的答案中包含两个结论。
    A:前两人将分别选16、17颗,前四人将选走15、16、17、18颗。
    B:第五人放弃任何特定策略,在剩余豆子中随便乱选一个数目。
    但这两个结论是怎么论证出来的呢?事实上,对A的论证中需要以B的必然性为前提,事实上A的推理过程包含着形如:“B是必然的;前四人是聪明的;所以前四人知道B;所以前四人将在B的情况下计算自己相应选择的生存率;所以前四人必将做出如此这般的权衡;所以A”。
    而另一方面,B又是怎么来的呢?事实上B又以A的必然性为前提,它的推理过程形如:“A是必然的;第五人是聪明的;所以第五人知道A;所以第五人将知道自己必死;所以B”。
    但这一循环的论证并不能真正证明A或B的必然性。顶多只是说明它们不矛盾。事实上,“非A且非B”也并不导出矛盾。
    如果学过模态逻辑,用模态逻辑的语言来表达一下,或许就更清楚了:Igeli证明的是“□A→B”(如果必然A则B)和“□B→A”(如果必然B则A)。但我证明了,“◇~A→~B/或写作~□A→~B”(可能非A则非B);“□~B→~A”(必然非B则非A)和“~□B→~□A”(并非必然B则并非必然A,换言之可能并非B则可能并非A)
    而对于第五人来说,他有选择的能力,他可以选择B这种行为方式,也可以选择~B的行为方式。他可以选择总是B,亦即□B,但也可以在任何情况下(他可以通过拒绝摸清剩余的豆子,而拒绝对情况的充分把握)都拒绝B,亦即□~B。
    而条件说第五人是绝顶聪明的人,所以他一定会选择最佳策略。
    而对于他来说,只要他选择~□B,乃至□~B,就可以获得生存的可能。而如果他选择□B,则必死。所以聪明的他一定不会使□B成立。如此一来□A也不再成立。
    这道问题的形式化还需要附加一些模态词,比如以“□1、□2、□3、□4、□5”分别表示“第一个人知道……”、“第二个人知道……”而“聪明人”的精确定义可以是:“□p→□1p”——亦即聪明人能够知道一切必然的事情。但这里的必然性指逻辑上的必然性,而不是事实上的必然性,也就是说即便当第五人进行选择时事实上他已经必死,他仍可以选择不知道这件事,如果他事实上的必死境况并非逻辑上的必然的话。
    总而言之我至少能够证明Igeli的证明是错误的,这一点在逻辑上是清楚的。当然,我猜想出题人的本意并不想搞成这样复杂,但这是另一回事。

  • 古雴

    2008-11-25 20:53:26 

    你没有理解博弈问题的原理。反正现在我作为第五人,选取的策略就是抽16或17个,你作为第一个人,策略也是选取16或17个。好了,现在我的策略是达到平衡了,因为无论我即便调整策略也不能获得一丝生机,所以我的策略就稳定在16或17上。但此时对于你来说并没有达到稳定点,你仍有更佳的选择,所以博弈还要继续进行,你稍微调整策略增加一点选15或18的概率,将导致你的胜率提升一点,所以你会继续调整策略。
    当然,我已经把该说的都说了。还不理解的话恐怕是因为你对博弈论的概念不够清楚。当然我也没太多的了解,不过我觉得这个问题并不需要过于深入的博弈论知识就能理解。
    如果你仍有疑问,可以向某个权威机构去咨询。
    当然,博弈论的一些假设,以及这类题目中“绝顶聪明”之类的概念,都是可以质疑的。如果你有针对性地对这些概念提出质疑,我还愿意再多看看,不然的话这个讨论就到此为止吧。
    也不要再和我讨论别的数学问题了,至少最近我不想再折腾了。

    对了,你不妨再好好想想那个“司令、工兵”对“炸弹、排长”的博弈。其它规则不变,我们改变一条规则:那就是如果排长碰上工兵只有一半的几率杀死对方,一半的机会则仍被工兵杀死。如果两个人都是聪明人也都知道对方是聪明人,会发生什么结果?采取什么策略?
    以下的推理哪里错了:
    乙出炸弹必死,所以聪明的乙不会出炸弹。乙必然出排长。
    所以甲出司令必活,出工兵的话有死的风险。聪明的甲当然必出司令。
    乙知道甲绝顶聪明,所以乙知道甲必然出司令。
    所以乙知道即便自己出排长也是必死。
    在明知两个选项都必死的情况下,乙没有理由偏向哪一个。所以乙将以各半的几率出炸弹或排长。(这里已经出现矛盾了)
    结果甲将有一半的几率被炸死。
    但聪明的甲知道乙只能以各半的几率出炸弹或排长。
    所以甲知道如果出工兵,将有3/4的存活率。
    3/4大于1/2。所以聪明的甲必出工兵。
    聪明的乙了解聪明的甲的选择,所以乙必出排长。
    ……
    哪里出问题了?关键是“当明知两个选择都必死时,就将以均等的几率随便选一个”这一假设是可疑的。关键在于,何谓“明知必死”?特别是,如果说这一必死的境况本身就与他在必死情况下将做出的选择有关,那么怎么就在没有决定自己在必死情况下将做出的选择之前就能够明确知道自己必死呢?特别是,如果规则允许蒙着眼睛,不充分了解可以了解得情报的情况下就做选择的话。那么当你还没有做出选择之前,你怎么就能够明知自己必死呢?
    你不能额外诉诸一个旁观者来看待这个问题,对旁观者而言,当第五人开始选择时,前四人的选择当然已经成为既定事实。然而关键在于,第五个人“可以”“不知道”。第五个人有权决定在不知道充足的情报时就做出选择。而问题是,你认定第一个人必选16或17时所用的推理中,是用到了第五个人只能随便乱选这一假设的。但这一假设并不成立,第五个人有充足的理由并不随便乱选,所以第一个人必定选16或17的推理是不成立的。
    那个“司令、工兵”对“炸弹、排长”中的一个悖论还是挺有意思的——在原题中再改动一下,比如乙手中有两张炸弹一张排长。如果乙是一个无可救药的白痴,他根本分不清炸弹和排长的意思,只会随便丢一张牌出来,也就是说2/3炸弹和1/3排长。而甲知道乙是个白痴,知道乙会乱丢一气,那么甲就将100%地选择工兵以确保最高的存活率即2/3(如果选司令就只有1/3存活率了)。于是白痴乙也获得了1/3的存活率。但是,如果乙不是白痴而是绝顶聪明的人,他将了解到出炸弹的话无论如何都是自杀,于是他决不会出炸弹。而甲若知道乙是个聪明人,他就知道乙必定只会出排长(注意,这是可疑的),于是甲就肯定出司令,结果比起1/3存活的白痴乙,聪明的乙反而必死无疑。这就是聪明反被聪明误吗?但聪明人为了求生有没有权放弃自己的知识呢?为什么白痴能做到的事,绝顶聪明的人反而做不到?

  • igeli

    2008-11-25 20:26:19 

    我认为你的最大问题是虚拟了5号会有一个最佳策略,但前4人却看出,在既定事实的情况下,5号是没有最佳策略的,用你的话说:“对手即便知道其策略,也将无可奈何,因为即便知道了对手的策略他也无法调整新的策略以提高胜率,此时博弈达到了平衡状态。”
    我觉得这个问题没有必要再讨论了,因为一切逻辑都已经非常清晰,平衡点也已经解出了,在这个平衡点下,任何参与者都不可能再改进自己的胜率。你如果对这个结论有疑问,可以向某个权威机构去咨询,我觉得这个问题还没有复杂到常人不能理解的程度。

  • 古雴

    2008-11-25 19:19:48 

    一道博弈问题如果有解,那么每人的策略都恰恰是最优的,并且其对手即便知道其策略,也将无可奈何,因为即便知道了对手的策略他也无法调整新的策略以提高胜率,此时博弈达到了平衡状态。
    比如说猜拳游戏的最佳策略是什么?就是各以1/3的概率出石头、剪子或布,平衡时胜率是50%。这一平衡位置可以理解为在无限次重复的赌博中达到的平衡。比如说你一开始采取的策略是100%出石头,那么经过许多回合后,我发现了你的策略,然后我按照你的出招概率重新调整策略,我就会越来越增加出布的概率。但再经过许多回合后,当你发现我越来越增加出布的概率时,你又会越来越增加出剪刀的概率……如此双方的策略不断调整,但这个调整却不是无序的,而是有方向的。你会发现双方为了提高胜率考虑而调整策略时,总是越来越接近于最佳策略,即1/3、1/3、1/3。最终当双方的策略都趋近于调整至1/3、1/3、1/3时,博弈就趋于平衡,双方即便看出对方的策略,也无可奈何——即便我知道你的策略是1/3,我也找不到更好的策略。当然,如果我知道你的策略是1/3,那么我重新回到100%石头的策略也能获得同样的胜率咯?那么怎么叫平衡呢?但没办法,博弈问题的平衡就是这个意思,这个就是最佳策略,你说达到平衡时再变回去,是胡搅蛮缠了。
    抓绿豆的博弈如果也按照一般博弈问题来理解,问题也就是这个策略的最终平衡在哪里?是否存在这一平衡点。现在第五个人就是采取16或17这一策略,你第一个人怎么办?第一个人肯定会朝着更高胜率的策略调整,而后面的几个人知道第一个人调整后的新策略后则又为了更高的胜率而调整自己的策略,后几个人调整策略后第一个人如果还有提高胜率的余地就还会调整策略……总之,最后如果有解,将会是一个平衡,此时每个人都知道别人的策略也无济于事,不可能再据以改进自己的策略了,这就是博弈问题的解。而在这里,即便说16或17并不是第五人的最终的平衡的策略,但如果它是博弈的中间状态,那么显然他的策略没有理由趋近于随便乱选这一策略。

  • 古雴

    2008-11-25 18:58:13 

    对啊,他没有办法提前宣称自己100%选16号。因为前人预测不出他的这一策略,因为似乎16与17具有某种对称性(当然我没有详细论证对称的是16和17,或许是15和16,不管,但很有可能是16和17),也就是说“如果前人知道第五人必定选16时”第五人的存活率,与“如果前人知道第五人必定选17时”第五人的存活率是相同的。那么前人就揣测不出第五人究竟是选16还是17。不过第五人选16号和他选1个的效果显然是不一样的,它们是不对称的,所以聪明的第五人有理由以更多的概率放在16和17上。
    在博弈问题中,一方的最佳策略之所以必须以某种概率的方式给出,是因为在相关情势下必须要增加自己的招法不确定性而增加自己的胜率。而如果增加一个选项的可能性将不会提高自己的胜率,那么这个选项就不会被考虑。也就是说,比如,拿1颗豆、2颗豆之类的选项是不会被第五人考虑的,因为即便增加这一选择的可能性,也不会给对手造成任何扰乱,从而也不会增加自己的胜率。然而16和17的选项却能够最大限度地扰乱对手,从而为自己增加胜率,因此第五人一定会偏重于选择16或17。这一策略是第一个人足以预见的。
    你对博弈问题缺乏了解吗?博弈问题可以转换为赌博问题。比如在这里抓绿豆的后果不是一次性地失去生命,而是负者输钱,游戏反复多次进行。那么如果让你做第一个人,而我做第五个人,你会采取怎样的策略?如果说你固执地坚持总是选16或17,那么你100次游戏中只能胜50次左右,而如果你愿意换一种方案,你的胜率将大大提高到75%,所以这就是你的最佳方案。如果你明知有75%这一更好的策略而固执地不采取,你怎么算聪明人呢?而我能够在貌似必输的绝境下获得一定的胜率,难道说这不是聪明人?你是说绝顶聪明人的胜率将不如一个只会抓16或17颗的傻帽吗?那么你关于“聪明”的定义究竟是什么?
    博弈问题当时我就出过一道最简单的:http://epr.ycool.com/post.2471508.html。其它博弈问题其实也都是类似。

      
    igeli

    2008-11-25 18:32:20 [回复]

    当然,这句话“如果他有机会活,摸清了也是50%,不摸清也是50%”,我也没去想是否为真。:)

      
    igeli

    2008-11-25 17:59:48 [回复]

    这个显然牵强—5号为什么选择16,17呢,当然就是他已经盘算过了,这和最后摸不摸清楚剩下多少已没差别也没有关系了,这也意味着,5号早就知道自己的命运了。如果他能够提前威胁其他人,比如宣称自己100%要选16号,他也许就会有很大的存活期望,可惜,他没法做到这一点。

      
    古雴

    2008-11-25 17:01:57 [回复]

    哈哈,你漏看一个条件! 
    条件说每个人可以摸出剩余的绿豆数,但没有说每个人“必须”摸出剩余得绿豆数。      
    第五个人的策略是只要有足够的绿豆,就摸出16或17颗,而不再去管剩余多少绿豆。这样的做法才是最理性的。

    第五个人有足够的理由支持他必须不去摸清剩余的豆数,并且有足够的理由支持他选择某些特定的数目。这才是最理性和最佳的策略。 
    就像那个司令、工兵对抗炸弹、排长的博弈。如果说条件规定乙必须看过牌之后才选择出牌,那么他无论如何不会选择炸弹这一自杀行为,所以乙只能出排长,于是甲总是出司令就好了,乙难逃一死。但是如果条件允许乙在不看牌的情况下瞎摸一张牌,而甲又知道乙可以这么做,那么最后博弈的结果就是乙有1/4的存活率。 
    在那个题目中由于条件含混不清,所以答案也说不清楚。但是在抓绿豆问题中的条件却是清楚的——我就是可以闭着眼睛摸!如果我闭着眼睛摸比我看清楚再摸生存率更高,我就不会多费功夫愣要去看清楚,这才理性! 
    第五个人多费力去摸清剩余的绿豆数是不理性的,因为如果他必死,无论摸清不摸清都会死,如果他有机会活,摸清了也是50%,不摸清也是50%,所以摸清楚剩余的绿豆数毫无意义,第五个人不会干这个事。而第一个人知道第五个人是理性的。

      
    igeli

    2008-11-25 13:46:59 [回复]

    我觉得应该这样理解问题—这样理解应该是理性的: 
    1)由于5号没有办法将自己的选择概率分部告知前4个人,前4个人应该按照对自己最有利的方式选择。 
    2)一旦形成17,16,18,15的情形后,5号所谓的报复策略将不再起作用,因为他已经没有最佳策略让自己逃脱死亡,这时他故意选择17,16的理由已经不再存在—如果你这时非要说他会选择17或16,那就不是理性的了,而是赌气:),而我们讨论的问题是不考虑感情因素的。 
    3)前4人都清楚这一点,所以他们的选择是稳定的,从而致5号于死地,换取自己最大利益。 
    这个结论应该是正确的。我们可以讨论其他问题了:)

      
    古雴

    2008-11-25 12:51:28 [回复]

    不是啊,前4人知道第五个人一定会采取最佳策略,这是这道题的前提。正如前三人知道第四人必然采取最佳策略,前二人知道第三人必然采取最佳策略……在此前提下,你才可能推理出前四人将得到17、16、18、15的结果。然而你的推理没有考虑第五人的最佳策略,你认为第五人只是绝望地放弃了任何策略。然而不是这样,第五人也是博弈的参与者。第五人将采取以极大的几率选择16、17这一舍身攻击的策略。这一策略对于第五人来说总是最佳的——如果必死,那么他选择任何数目结果都是一样的,也就是说,他选择其它数目时也不会比选择16或17更好,所以他总有充足的理由贯彻这一策略。第一个人了解到这一点,所以就不得不放给第五人一线生机。     
    而第五人的策略之所以必然是以极大的几率选择16或17(或许是16和15?但总有某几个数是重心),并不是随便找了两个数字。如果第五人以一定的几率选择其它数字,平衡状态将可能会被打破,他将不可能获得50%的生存率。想要有可能获得50%的生存率,第五人没有其它办法。 
    简而言之,在这个人人都绝顶聪明的博弈中,前四人是有可能知道第五人的概率分布的。虽然我没有证明第五人的50%存活率是最高的,但是他至少有这样的存活率。 
    好了,这道问题到此为止。

    当然我这个肯定不是最终答案。因为这里还是会有问题,那就是第四个人似乎未必会给第五人留活路。前三人选18、15、17时,第四人选13或16的存活率都是50%,而他似乎不像第五个人那样,即便在存活率相等的情况下也有额外的理由支持特定的选择,而且第四人即便是在原先你的思路下的存活率也恰好是50%,他的处境是比较微妙的,所以看来这个平衡还不稳定。但我们毕竟看到了第五个人存活的希望。或许第五个人的最优策略中还要带有13和20等选项,通过微妙的逼迫使得第四人不得不让道?无论如何,即便说第四个人在存活率同等的情况下将以同等的概率做出选择,对于第五人来讲仍旧有理由始终贯彻舍身策略。

      
    igeli

    2008-11-25 12:00:12 [回复]

    对前4人来讲,由于不知道第5人的概率分布,那他们就只能根据自己的主观判断—信念,来进行决策,这样将得到17,16,18,15的结果,不是吗?

      
    古雴

    2008-11-25 10:23:31 [回复]

    第五人的最佳策略没准并不复杂,或许就是以各半的几率选择16或17(只要剩下足够数目可选)。然后前两人都知道第五人的最佳策略,如果第一个人选16或17就只有不到50%的存活率,但选择15或18则将有超过50%的存活率,所以第一人的最佳策略是选择15或18,第二人则依据第一人的结果选择18或15。然后第三个人可以选择16或17,这样可以得到50%的存活率,也可以选择14或19,这样的话最后还是50%的存活率。第四个人依据第三个人的选择,如果第三个人选择16或17,那么第四个人就得选择14或19,反之第三个人选择14或19时第四个人选择16或17,这样第四个人也是50%的存活率。第五个人也是50%的存活率。如果第五个人死了,那么第一第二个人都将存活,如果第五个人没死,那么第一第二个人中间将有一个人死。也就是说前两个人的存活率是75%。

    噢对了第四个人的策略不能是选14或19,不然的话第三个人究竟是选的16还是17将被第五个人算出。所以第四个人应该选择在13或14以下或19或20,第三个人选16时第四个人选14或20,第三个人选17时第四个人选13或19。使得第五个人无法揣摸究竟是16还是17被占。这样存活率仍是75%、75%、50%、50%、50%。除了第五个人的策略是凑出来的,其余四人看起来都不得不按此方案选择,否则难以获得更高的存活率。 
    第三个人不可以采取摸走大多数绿豆只剩两颗的策略。因为这样的话他得到的将不是50%的存活率,而是来自必死的第四人的“报复”(第三人如果不给第四个人活路,第四个人必定拖他垫背,所以第三个人必须给第四个人留出活路才行。)

      
    古雴

    2008-11-25 10:07:07 [回复]

    反正这两天被这题目搞得睡眠不佳,我是放弃再继续折腾下去了……讨论就到这儿吧……

      
    igeli

    2008-11-25 09:58:13 [回复]

    如果找不到这个平衡点,估计选择就会混乱了,出题者也许根本就没想这么多。

     
    igeli

    2008-11-25 09:55:11 [回复]

    我觉得讨论有点引人入胜了:) 
    假如5号公布出一个剩余数字和自己选择概率的对照表,那么,他真的可能活下来,但是这个工作量似乎大概太大了,我想不出好办法解决这个问题哦,你能否想出好的办法给出确切的解答:) 
    另外一个没有考虑成熟的想法: 
    公布一个对照表,估计很容易找到一个平衡点;但是,如果不存在一个事实上稳定的平衡点怎么办呢?因为囚徒之间不能进行信息交流,也就是说,5号要想人为制造一个平衡点(公布一个表格)是不可能的。

      
    古雴

    2008-11-25 04:44:10 [回复]

    我再出一个相关的简单题目看看: 
    甲乙两个人博弈,甲手中有两张牌:司令和工兵。乙手中有排长连长团长营长旅长师长军长和炸弹(工兵能拆除炸弹,司令则与炸弹同归于尽)。双方的最佳策略是什么? 
    如果甲出司令,那么乙无论出什么都难逃一死。那么是否甲的最佳策略就是出司令,而乙只能在手中的牌里随机乱摸了吗?当然不是。乙的最佳策略是以较大的概率出炸弹。这样甲一旦出司令就有较高可能会被炸死。而甲所考虑的首先当然是自己的活命,所以他不会贸然出司令。当然乙不可能以100%的概率出炸弹,这样的话甲总是出工兵好了。于是最佳策略是双方博弈的平衡点。假设甲乙x的概率出司令,1-x的概率出工兵。乙以y的概率出炸弹,1-y的概率出其它牌。对甲而言,达到平衡状态时应有xy=(1-x)(1-y)。而对乙而言,应争取存活率即(1-x)(1-y)达到最大。结果解得x=y=1/2。也就是说,乙的最佳策略是以50%的概率出炸弹,这样如果甲是一个聪明人,乙将获得25%的存活率。 
    抓绿豆问题复杂得多。但未必找不到类似的平衡点。

    不过这道题仍是个伪的博弈问题。作为博弈问题而言这道题也是无解的,因为只有甲的选择平衡了,乙却平衡不了……当然这个问题其实反映了某种悖论在里头…… 
    不过在更复杂的抓绿豆问题中,是大有可能出现真正的博弈问题的解的。关键是最后一人决不会乖乖扮演被动的角色,而要以舍身攻击来威慑前面的人不得不为最后的人留出生机。事实上在这场博弈中第一个人比最后一个人而言并没有太大的优势。事实上第一个人的优势仅仅是先手,但后手也有后手的优势,最后一个人将参考前四人的结果后作出选择,而对第一个人而言后四人的选择则仍然是不确定的概率状态。

      
    古雴

    2008-11-25 03:45:57 [回复]

    啊对了对了。作为一场博弈,最后一个人为什么会乖乖地听天由命随便乱选?事实上在这道题中,既然五个人都是绝对聪明的人,也就意味着前面的人将能够了解最后的人的最佳策略。而最后一个人的最佳策略绝对不是在1到34之间随便任选,而是,比如说以极大的概率选择16或17,或者以极大的概率选择18或15……。这并不是因为他与前几人有私仇之类,而是只有采取这样的策略,才可以保证自己获得存活的可能。第五个人是聪明人,所以他一定会选择更可能让自己存活的策略,而第一个人既然知道第五个人的策略,那么他就不会贸然选择16或17,因为这样的话他将很有可能被第五个人害死。所以他必须以一定的概率选择其它的个数,而这样的话就将给第五个人留下生存的空隙。

    因此这个博弈是可能找到平衡点的。那就是第一个人以某个概率选择16或17,又以某个概率选择19或14。而最后一个人以某个概率选择16或17,以某个概率选择18或15,等等。 
    这样一来,比如当第一个人选择19时,第二个人也不会注定选18,因为第五个人还可以在剩下不是34颗,而是30颗时采取另一种策略,就是一旦剩下30颗,就意味着很可能是第一个人选19第二个人选18的情况,那么第五个人的策略可以是当剩下30颗时以巨大的概率选18力争害死第二个人,这样的话第二个人就不会贸然选18了。——第二个人的策略也是在18或14等几个选择之间的某种概率分配。于是,一旦出现第一个人选19第二个人选14、第五个人选16或17的情况,第五个人就得以存活。 
    总之第五个人是有存活的可能的,博弈的平衡点是可能找到的。

      
    古雴

    2008-11-24 23:29:46 [回复]

    嗯……其实第二个人的处境似乎与第一个人是一样的。这里涉及一个悖论:如果放弃自己的选择能力,而把选择权托付给别的东西——第一个人托付给随机数生成器,第二个人则托付给第一个人和随机数生成器,而自己完全不再做出选择,也就是说,如果他者所做的选择将导致他的必死,他也会照做。如果这样的话,他将获得更高的存活率。然而问题是,如果人都不愿意放弃自己最终选择的自由的话,那么第一个人即便在看到随机数生成器显示他应当选4(送死),或者第二个人看到第一个人选4时,都绝不会乖乖地去选择必死的方案。于是博弈策略就不可行。如此一来,收回自由的代价是存活率的降低…… 
    另外,这道题的枚举论证仍是可能的,那就是假设每个人以Xi%的概率选择I颗豆,然后把各种结果展开出来,最后按博弈问题的解法找鞍点……不过这似乎太过庞大了。。

    不过我所说的这个博弈方案无论如何只是一个伪装的方案,博弈的话最终如果达到平衡点,则每一个选项的胜率应该是一样的。但这里显然达不到。但关键是证明啊。

      
    古雴

    2008-11-24 22:46:36 [回复]

    哦对了,可以对称一下,第一个人可以以同样微小的概率选择4或29,以及15或18。第二个人的应对也是对称。这样的话就可以使得16和17有同样的几率被第三个人占据,并且留给第五人的总是34。嗯。

    呃,第一个人不需要增加选29的可能,而只需要增加18这一选项就行,而第二个人则增加4+31这一微小的可能性~ 
    当然这道题无论第一人选择4还是29之类,到了第二个人这里已成既定事实的话,第二个人似乎是不可能与之配合的。但有没有可能逼迫他不得不配合呢?我找不出对于这种策略不可能存在的证明。用枚举法一一验证是不行的,因为现在的策略不仅仅是一个单一的选择,而是一套微妙分配的概率方案,它的可能性是无穷的。

      
    古雴

    2008-11-24 22:33:54 [回复]

    关于如何变成博弈问题,我可以举一个例子:就按着这道题来举吧: 
    第一个人采取如下策略:99.999……%的概率选16,然后0.00001%的概率选4,以0.0001%的概率选15;第二个人则与第一个人配合,当第一个人选4时,以99%的概率选27,以1%的概率选29(如果他选别的,死亡率也都极高,他可能不得不配合,尽管我还没有仔细分析。)。当第一个人选15时,第二个人当然选16。 
    如果前两人选15+16或4+27时,三四人会选17、18。而前两个人都是抓走16+17或4+29时,第三和第四个人会选15、18(我都没有仔细分析)。 
    关键到了是最后一个人,留给他的总是34颗豆,然而现在他的存活率不是0%了,而是有一线生机,尽管比0.00001%更小。如果第一个人选的是4,那么最后一个人选择5、6、7、……等,都将存活。然而他却不会选16或17,因为即便当第一人选4的时候,由于第二个人有99%的概率选27,也就是说16和17被前四人中某个人占据的可能性要远远高于5、6、7等被占据的可能性,因此最后一个人将更倾向于选5、6、7等,而几乎不可能选17。 
    也就是说,尽管对第一个人来说,选择4颗是近乎自杀的行为,然而他只要给自己增加0.000000……1%的选4颗的可能性,就可以促使第五人极大地降低选16或17的可能性。也就是说,第一个人的存活率就此从33/34提高到99.9999……%!

    即便这个策略仍有漏洞而不可行。但我讲出来主要是为了展示某种可能性——通过某种复杂的博弈,有可能给于第五人以一线生机从而减少与第五人重复而处死的可能性。 
    即便我举不出这样的例子,但如果你并没有论证出这种例子必然不存在,所以你的论证是不严密的。

      
    igeli

    2008-11-24 21:36:34 [回复]

    我想那种完美的策略是不可能存在的。 
    事实上,由于有非常多的可能,所以我们之前定性地排除了1号选20以上的情况,那样他成为最大的可能性很大,你若有时间,也可以一一给他定量:),当然,也可以把15以下的情况都计算一番。至于是不是要在某些可能性里按概率加权—如你说的成为一个博弈问题,我没有想出这样做的理由,把1号的最优策略分出一部分进行劣化,无论这个比例有多大,都会使1号整体存活概率降低吧?你能想出相反的例子吗?

      
    古雴

    2008-11-24 18:18:48 [回复]

    一旦涉及到概率,策略问题就有可能成为“博弈问题”,也就是说,一旦涉及到概率,“最佳策略”就未必是一个确定的选择,而是一组概率的选择。比如说“某个人的最佳策略是以90%的概率选择A和10%的概率选择B”。

      
    古雴

    2008-11-24 18:08:33 [回复]

    我也相信最佳策略是16或17颗绿豆,问题是论证不够严密。毕竟第一人选16或17颗绿豆时存活率也并不是100%。但会否有这样的情况:因为我们并没有证明当第一人选的不是16或17颗时,后几人也必定会选择连续的数字,所以或许当第一人选A颗时,最终导致前四个人的选择中仍有空隙,于是第五个人仍有一线生机,那样的话第五个人就不会乱选,而是会,比如说他必须在B或C中博一博运气,而如果A既不是最大或最小,也没有与第五人撞车的危险,那么第一人的存活率就100%了。 
    直觉上看这种完美的策略似乎不太可能,不过仅按你所给出的解法并不足以证明这种策略不存在。

      
    igeli

    2008-11-24 16:10:12 [回复]

    想通了,那个数字问题几乎是个纯数学的问题,没啥意思,不再这里讨论了。

      
    igeli

    2008-11-24 15:15:14 [回复]

    也就是说,虽然在讨论时提到方案1,方案2,事实上还有方案8,9,10… 
    但是由于那些方案都不是最佳策略,因此都不会作为可能来考虑,也不会加权到结果中。

      
    igeli

    2008-11-24 15:11:28 [回复]

    有意思的想法。不过,由于这些人都是极聪明的,4号发现前面不是最佳组合17,16,18时,他应该能判断一定有人玩花招,最可能的就是3号,因为17,16对1,2号是最优的,那么,他可能判断出3号的数目,从而致3号最不利地位。3号因此不敢冒险,否则就不太理智了。 
    除17,16的组合应该是不可能出现的,否则他们就不是聪明的(与题设相矛盾),或者就是有人耍花招,那样冒太大风险,也是不理智不聪明的,由于可以被后面的人算出,所以都应排除在外。 
    我对那个100个数字的题目有了些想法,等下写出来和你商讨:)

      
    古雴

    2008-11-24 13:26:11 [回复]

    你的解法和答案都和我一样。不过我自我感觉似乎不太严密。 
    关键是后三个人何以能够断定前面的人选择的是连续的号码?因为他们只能摸出前三人的摸走的总数,如果说不假思索地认定前三人一定选连续的数,第四人可能要上当。 
    比如说前两人选了17、16,而第三个人耍阴招选个21。这样的话第四人是否会错以为前三人选的是19、18、17?这样的话第四人就会选16,从而与第二人撞死,那么第三人选了21存活下来了,而他选15的存活率只有19/34。 
    进而,第二个人考虑到第三个人可能玩阴招害死他,那么他是不是也不再敢轻易地选16?……

      
    igeli

    2008-11-24 12:51:34 [回复]

    附注:几个有趣的特例: 
    1)1号选100,他自己死,救了其他4人; 
    2)1号选99,1,2号必死,其他3人活 
    3)1号选98,2号必死,但可以选1号或3号垫背。

      
    igeli

    2008-11-24 12:46:03 [回复]

    (接上,第3部分)没想到要分3块才行:) 
    方案三(1号选17) 
    1号选17时,如果出现17,16,15,14数列,5就有38种选择 
    1死:5选17,或小于14的数目,共14种,存活几率24/38 
    2死:5选16,1种 活命概率37/38 
    3死:5选15,1种 活命概率37/38 
    4死:5选14,或大于17的数字,共22种,存活几率16/38 
    对4号来说,由于16/38<19/34(参考方案二中选18),所以他不会选14,而会选18,出现17,16,15,18排列;3号当然知道,如果出现17,16,15这样的排列,4号一定不会选14而会选18,这样3号存活几率就只有17/34,由于17/34<19/34,所以他会放弃选15,抢先选18,从而逼迫4号只能选15,这样1号达到了逼迫别人把自己夹在中间的目的:最终前4人的选择是17,16,18,15 
    1-5号存活几率是:33/34,33/34,19/34,17/34,0% 
    结论:1号选17(或16),2号选16(或17),活命几率最大,约97%

      
    igeli

    2008-11-24 12:44:27 [回复]

    (接上) 
    方案一(1号选19) 
    据上述推理,1号选19时,将出现19,18,17,16这样的排列,此时5有30种选择:      
    1死=(5选19,或小于16的数字)共16种,1号存活几率14/30(显然1号最不利) 
    2死=(5选18)共1种, 2号存活几率29/30 
    3死=(5选17)共1种, 3号存活几率29/30 
    4死=(5选16,或大于19的数字)共12种,4号存活几率18/30 
    方案二(1号选18) 
    1号选18,将出现18,17,16,15的排列(没人选19,因14/30会最小),此时5有34种选择: 
    1死:5选18,或小于15的数目,共15种,存活几率19/34 
    2死:5选17,1种,存活几率33/34 
    3死:5选16,1种,存活几率33/34 
    4死:5选15,或大于18的数目,共17种,存活几率17/34;(显然17/34>14/30)

      
    igeli

    2008-11-24 12:40:38 [回复]

    可能是太长了,我只能分两部分试试: 
    我的结论一样,是自己的解答,不知道推理中有无漏洞,请指教:) 
    显然,处于两端(最大数或最小数)的人死亡概率较高。1号最先选,他不应选超过20的数目,否则,他会给2号留下非常好的策略:选一个比他小1或接近的较小数目(在特殊情况下,2号甚至可以保证自己不死,比如1号选了35,他就选34或33,因为剩下的总数比他小,2号就不会死了。1号若选21,他就选20,这样可保证后面有人比自己小),这样2号就处在一个非常优越的地位,至少保证自己不是最大或最小,而1号就面临可能是最大数的危险。同样道理,234都不会第一个去选超过20的数目,20会是前4个数字中最大的一个,1号的策略就是选一个数字,逼迫后面的人把他夹在中间,显然,选20对他是不明智的。 
    1号选择一个数目后,2号如果可能,一定会选择一个和1号紧临的数字,这样他就不会给3号留下中间数的极佳位置;据此,3号可以判断前两个数字是什么组合,根据同样的理由,他也会紧邻这两个数字选一个;同样,4号也会在上述三个连续数字的两端选一个(这4人不会选重复数字,那样意味着自杀);这样可以确定,前4个数字是4个连续数字。5号无论选什么数字,都必死—他如果选两端,就是最大或最小,如果选中间,就会和1234中的一个重复;由于每次都是死两人,所以5号会随机选一个数目,就会有一个(且只有一个)垫背的和他一起死。

      
    igeli

    2008-11-24 12:39:09 [回复]

    发表不了评论,网站有问题?

      
    古雴

    2008-11-23 13:35:00 [回复]

    凑了一下觉得第一人应该抓16或17个 
    你公布答案吧~

      
    igeli

    2008-11-23 09:16:49 [回复]

    是的,后面的人只知道前面的人一共拿了多少颗。 
    但是那个50%的概率显然不是最大的,因为这样的话,第4,第5个人的存活概率已经是100%了。:)

     
    igeli

    2008-11-23 09:10:48 [回复]

    抓绿豆的条件完全给足。 
    我想你说的那种走投无路的情况下,他的选择应该是随机的—因为题目没有说他特别恨那些人,只是说,他们喜欢杀人,如果能让更多的人和他一起死,他肯定不会放过的。

      
    古雴

    2008-11-22 21:06:59 [回复]

    我一开始感觉理应是第二个人存活概率最大,不过后来我替第一个人想到一个策略,那就是一下子抓走98颗绿豆,然后第二个人要么抓2个要么抓1个,怎么着都是死路一条。抓两个的话拖第一人下水,抓1个的话拖第三人下水。如果说在必死情况下第二个人的选择概率各是50%,那么第一个人抓98颗豆就能保证自己有50%的存活率。这个概率对第一个人来说貌似挺高了……

      
    古雴

    2008-11-22 20:56:35 [回复]

    抓绿豆问题的条件是否给全? 
    是不是说抓的时候只能知道剩下几颗,也就是说,比如第三个人抓豆时能知道前两个人总共抓走了多少,却不知道他们分别抓走了多少?另外,这是个概率问题?那么如果当某人走投无路时(知道自己抓几个都是死)他将以何种概率进行选择?是说此时每一种选择的概率是平均的?

      
    古雴

    2008-11-22 20:12:29 [回复]

    别说什么头脑非凡了,都四五年没做奥数了,思维大大迟钝,原本应该早反应过来的。而且就算是几年前我的头脑在全理班那群牛人面前实在也毫无立足之地…… 
    你的题目似乎有点难,而且现在我也早没有不眠不休琢磨数学题的兴致了,想了一个钟头也没任何思路,罢了。。

      
    igeli

    2008-11-22 18:54:10 [回复]

    你果然头脑非凡,那个念头(乙丙看法不一)在我脑中闪现了一下,但随即丢弃了,现在看来,很悬:) 
    我倒是有一个一直没有好办法解决的问题,你愿不愿意做做消遣? 
    说是在100人前额上随机写一个1-100的自然数,他们彼此能看到别人的数字,但看不到自己的数字,他们该采取怎样的策略,保证至少有一个人能猜对自己头上的数字?写数字之前大家可以商量,写上之后,彼此就不能再透漏其他信息了。 
    网络上没有发现好的解答。 
    另外一个趣题: 
    5个囚犯,分别按1-5号在装有100颗绿豆的麻袋中抓绿豆,规定每人至少抓一颗(被动选0的囚犯自动免死),在没有重复数目的情况下,抓得最多和最少的人将被处死,而且,他们之间不能交流,但在抓的时候,可以摸出剩下的豆子数。问他们中谁的存活几率最大? 
    提示: 
    1)他们都是很聪明的人 
    2)他们的原则是尽可能保命,再去杀人 
    3)100颗不必都分完 
    4)若有重复的情况,将代替最大最小者被处死 
    请多交流,很高兴和你讨论问题:)

      
    古雴

    2008-11-22 18:43:08 [回复]

    嗯,貌似你的方法没错。

      
    古雴

    2008-11-22 18:39:31 [回复]

    哦,似乎D可以一步分完?按你之前说的方法略为改动一下就行了?

      
    古雴

    2008-11-22 18:32:18 [回复]

    你的办法看起来还算不错,不过关键是被裁去的部分还有待分割,剩下来的这个D还需要重新分配,这样的话就无法确保在有限步内完成分配,尽管分歧确实能够越来越小。

      
    igeli

    2008-11-22 18:23:16 [回复]

    把叙述稍微简化一下: 
    当乙,丙同时认为A最大时,假设乙认为A>B>=C,让乙分割A为A-和D,使B=A- 
    现在让丙从A-,B,C中选择,如果丙没有选择A-,则乙必须选择A-,剩下一份留给甲。 
    以下分D说法不用修改。怎么样?

  • igeli

    2008-11-22 18:07:30

    你真的没明白?规定乙选A-,只有在丙选了C的时候。而A-当然是乙裁出来的。
    他裁的均不均匀没有关系,只要他认为均匀就可以了,丙绝不会说你裁的多了还是少了,因为丙第一个选。
    估计被我说晕了

  • igeli

    2008-11-22 18:00:11 

    哈,你大概晕了:)
    当第三个人认为A>C>B,而第二个人认为A>B>C时,我们让第二个人分,使A-=B,这时,留给第三个人的选择是A-,B,C,他可以随便选,我们不保证第三人会认为A-比C小,也许会大,但他有选择权,他会在A-和B甚至C中选出认为是不小的那份来。
    你的下面那个留言的第一句话,作为一个条件又错了(如果一个人愿意选择某一部分,他肯定要确信这一部分不小于三分之一。),这个结论在完全分配完毕后才正确,而在中间的分配中,每个人只关心我得到的总量不比其他两人少,要>=总数的1/3,还得等下一轮分配。
    怎么样?

  • 古雴

    2008-11-22 17:36:17 

    而且,你这个“规定第二个人必须选A-(他认为A-=B>C)”中,这个A-是谁裁减的?如果说乙减去A使之等于B,丙可未必认同,丙可能说乙减得远远不够,非但不等于B(在丙看来最小的),而且仍旧比C还大嘛!你没办法解除分歧。如果是丙裁减的,乙当然也可能不认同:减掉太多了!

  •  

    古雴

    2008-11-22 17:27:35 [回复]

    要注意,在你的条件下,如果一个人愿意选择某一部分,他肯定要确信这一部分不小于三分之一。因为如果他知道自己得到的小于三分之一,那么他就会认为另两个人中至少有一个人得到的大于三分之一,也就是比自己多。 
    所以如果说第三个人认为A>C>B而且是A>1/3>C>B,那么他就绝不愿意选C,因为它不到1/3。 
    总之你必须解决这样的情况:甲分成A、B、C后,乙丙两人都认为A是最大的,同时都认为B、C两块都不到1/3,而且关于B、C之间谁更大并不一致。

      
    古雴

    2008-11-22 17:18:34 [回复]

    如何保证第三个人认为A-比C小?

      
    igeli

    2008-11-22 17:15:12 [回复]

    哈哈,你果然头脑非凡! 
    但是这样丝毫不影响分配,第三个人可以选择C(在第二人看来最少的那份),但是规定第二个人必须选A-(他认为A-=B>C),从而留给第一个人B,之后分配原理和上述一样。

      
    古雴

    2008-11-22 13:34:15 [回复]

    虽然没仔细看,不过你的分发似乎不行。关键是当另两人都认为A最多时,他们两人未必对B和C哪个多达成一致,也就是说,必须考虑第二个人认为A>B>C,第三个人认为A>C>B的情形。这样的话如果第三人只能在A-和B中选,就可能认定拿到C的第一人比自己多。

      
    igeli

    2008-11-22 13:20:46 匿名 58.31.177.132 [回复]

    真巧,我正想来说明那个对n个人的解法存在同样问题,您已经发现了:) 
    解释一下3个人分桃汁的问题: 
    假设第一个人按自己认为均等的方式分成了A,B,C三份,现在由后两人选择,出现两种情况: 
    一、一个选A,另一个选B,非常好,C归第一个人,大家相安无事。 
    二、两人同时选A,即认为A>B>=C 
    那么,由第二个人将A的一小部分倒出到容器D中,剩下的记为A-,第二人认为A-=B 
    现在由第三人在A-与B中选择,剩者归第二人,C归第一人,三人都不认为有人比自己多。 
    现在,由拿了B的那个人(假设是第二人,若是第三人,情况与此相仿)将D分成相等的三份,由第三人首先选,然后第一人选,最后由第二人选,这样,三人都不认为别人比自己分得多: 
    第一人认为第三个人(A-)拿到所有的D也不过和自己相同(C=D+A-),现在他只拿到其中一部分,其总数还不如自己的C,而自己又可以选剩下两份中较多的,不会比第二个人少。 
    第二个人认为自己的B不少于A-和C,自己最后拿的那一小份与其他俩人一样,所以没有人比自己多。 
    第三个人认为自己的A-不少于B和C,而自己在最后三份中首选,没人会比自己多

  • 古雴

    2008-11-22 01:56:30 

    另外,这个问题当时被推广到n人的情形:见http://epr.ycool.com/post.2471356.html 。不过按照那个通解,也是绝对不能满足阁下“假设每人都不希望别人比自己多”的附加条件的,不过那个通解的好处在于每个人拿到手的都是他自己认为恰好是1/n的那部分,不多不少。然而显然不能保证其他人也都分得恰好一样,所以最后结果肯定会发现有人自己更多,这无法避免。我实在看不出在加上你的条件后这道题还有可能有解,请指教!

  • 古雴

    2008-11-22 01:43:33

    哦,对不起。看来确实是我的问题(睡梦中惊醒。。),出题的时候太久远了,忘记审查问题了。题目中应当限定说每个人最终所关心的只是自己所得那份是公正的。不过如果不加这条设定,而是如你所说假设“每人都不希望别人比自己多”,将有什么办法分桃汁呢?

  • igeli

    2008-11-21 14:21:03 匿名 221.219.245.20

    偶然看到你的博客,真不错,很喜欢那些趣味题目。哈哈,终于被我发现一个错误:
    分桃汁问题:“如果丙认为最大的是B+或C+,不妨设丙认为最大的是B+,则把C+分给甲,把A-分给乙,即可。”是不可以的,比如:乙把桃汁分成1/8,4/8,3/8(数字夸大是为了举例清晰),而把3/8分给甲时甲是不会满意的(假设每人都不希望别人比自己多)。再往下就没有想了。
    我倒是另有一个好方法来分这些桃汁

  • 关于 古雴

    胡翌霖,清华大学科学史系助理教授。本站文章在未注明转载的情况下均为我的原创文章。原则上允许任何媒体引用和转载,但必须注明作者并标注出处(原文链接),详情参考版权说明。本站为非营利性个人网站,欢迎比特币打赏:1YiLinDDwvBLT19CTUsNHdiQhXBENwURb

    发表评论

    电子邮件地址不会被公开。 必填项已用*标注