@ 2012.12.30 , 10:37
84

史上最难的逻辑题

[-]
#题目不是上面这张图......

现在马上就要到新年了,蛋友们是在上班呢还是在打发无聊的周末呢?无聊的话,试试下面这道逻辑题吧。在理想情况下,你差不多得把一上午花在这道题上。

题目在此:

现在有三位神祗,名字分别“真实”、“虚伪”、和“任意”,但是你并不知道哪位神祗名字是什么。“真实”永远说真话,“虚伪”永远说假话,而“任意”所说的话是真是假则完全是随机的。现在,你需要辨识出这三位神祗的真实名字,只能问3次答案是“是”/“否”的问题,每个问题只能针对一个神祗(但你可以问多个神祗同样的问题)。神祗能听懂你说的话,但是祂们只会用自己的语言回答你的问题。在他们的语言中是否分别为da, ja,但是你也不知道哪个是“是”,哪个是“否”。

在1996年,美国逻辑学家George Boolos最早给出问题的解答(很不幸,他给出解答的不久之后就去世了。)这个问题的难点在于它将“语言不通”、“真实与虚伪”和“随机性”三者融入到一起。哲学家声称,破解难题的勇士们将能透彻地理解逻辑学的本质。

但是,一个上午废了N张草稿纸也解不出来是么?不用着急,我们有答案。(痛戳答案

答案打不开?打开之后全是看不懂的鸟语花香?别急,这是中文版答案

本文译自 Gizmodo,由译者 pwwp 基于创作共用协议(BY-NC)发布。


给这篇稿打赏,让译者更有动力
支付宝打赏 [x]
您的大名: 打赏金额:

4.4
赞一个 (61)

TOTAL COMMENTS: 84+1

[2] 1 »
  1. 2194704

    看了R&R的解答。發現我上面的解答(@Sinya)還是最好的。

    Rabern的答案裡面自己創造出了mental state這個東西。但實際上要定義mental state需要附加一個條件:也就是Random在回答問題前先flip a coin然後再決定說真話還是假話,而且flip a coin之後就不變了。

    如果Random回答問題是先想出答案之後再來flip a coin決定說真話還是假話,甚至或者說Random沒看到一個問題就flip一次——這樣也是符合題意的,但是這樣子Random的所謂mental state就是ill-defined了。所以R&R裡面只有“Truely Random”的部分才是沒有曲解題意的嫌疑。

    至於explode gods’ head,那這樣的問題還算well-defined的yes-no問題麼?已經算yes-no-explode問題了吧。。。

    所以說來說去還是我的解答(也就是R&R裡面第3部分的解答)又簡單又正確又符合題意。

  2. 2194636

    不看答案先發一下我的解答。首先“最難的邏輯問題”這個說法只是噱頭,這個問題根本不難,也就十分鐘左右的事情。隨便搞個邏輯電路給你求可滿足性玩玩你就受不了了。

    樓上@von 說法是對的。我之前提出解答的全部是[哔–],大部份解答都不符合題目要求,符合要求的也錯了。

    =========================================================================

    三個神分別編號1、2、3。問的三個問題分別編號X、Y、Z。

    首先向神1詢問問題X,這個問題可以使得:只要神1不是Random,那麼如果神2就是Random,那麼神1回答ja,否則回答da。
    詢問完X之後,如果回答是ja,那麼我們可以確定神3不是Random。如果回答是da,我們可以確定神2不是Random。

    不妨假定神3不是Random. 那麼我們問神3問題Y,這個問題可以使得:如果神1是Random那麼回答ja,否則回答da。
    詢問完Y之後我們就可以確定1和2誰是Random了。

    之後我們向神3詢問問題Z,這個問題可以使得:如果神3是True那麼回答ja,否則回答da。
    這樣子我們就可以確定神1、2、3的名字了。

    —————

    接下來只要解決X、Y、Z三個問題分別如何構造就可以了。構造如下:

    X:(神2是Random) xor (如果問你“1+1是不是等於2”你一定會回答da),是嗎?
    Y:(神1是Random) xor (如果問你“1+1是不是等於2”你一定會回答da),是嗎?
    Y:(神3是True) xor (如果問你“1+1是不是等於2”你一定會回答da),是嗎?
    ,其中 “(A) xor (B)” 相當於 “(A)是真的且(B)是假的,或者(B)是真的且(A)是假的”。

  3. 2168340

    解这个题的核心就是构建复数的“与判断”问题,
    比方说:

    “小红是女孩 并且 小明是男孩 并且 他们两个谈恋爱 并且 今天北京晴天 并且 今天台湾是晴天,是吗?”

    会得到一个逻辑是否的布尔数值。

    楼上所有用单独问题的,在三个问题之内,统统都解不了这个复杂的题目。

  4. 鸡蛋
    @5 years ago
    1871769

    我把解答看了,有很多延伸很有趣的,都写在那篇贱贱的论文里。

    首先要明确的是,随机之神究竟是怎么回答问题的。原题作者的表述是它在回答问题前会先在心中随机的决定接下来是讲真话还是假话。如果只是这样会让解答简单得多,因为有时说真话有时说假话的问题我们见得很多了,也好对付。而原来那个复杂的解答,可以应付随机之神完全无视逻辑只掷硬币看结果随机说da ja的情况。

    然后,三个问题并非极限。因为还可以构造出引起悖论的问题,让神祇无法回答。这样da ja 无法回答就是三种不同的输出了。如此只要两个问题就能搞定。

    最后搞笑的一点是,其实在某种语言里,da和ja都是表示是的意思。作者故意的。

  5. 1709749

    这个不是悖论说的经典案例么,根本就没有正确答案的,条件不充足

  6. lucky毛毛
    @5 years ago
    1709645

    连题目都看不懂的飘过

  7. 长腿等等喝酸奶
    @5 years ago
    1708337

    @中中:
    重点补充说明,只能问三个问题,你第一问就把三个问题问完了,真是题目都没看清楚的大师啊

  8. 1704371

    另外同时问3个神一样的问题是不是只用掉一次机会?
    总觉得题目有歧义..

  9. 1704367

    “每个问题只能针对一个神祗” 这是不是说只能问针对神的问题,其他问题都不能问? 就是说什么 da是否、1+1是不是等于2之类的那种问题都不可以问?

  10. 中中
    @5 years ago
    1704293

    重点补充说明:
    我的思路是假定三人的位置是固定的,以便于简单的说明我的思路。
    实际上三人的位置是不确定的
    但思路是一致的,所以不再重复

  11. 中中
    @5 years ago
    1704283

    不看答案了,先献上自己的答案
    用时(估):心里推理用了3分钟,语言组织发表用了10分钟

    假设这三个人分别为A,B,C固定站位

    第一问:你是“真实”吗?
    得到回答分四种:1a(da,da,da) 1b(da,da,ja)1c(ja,ja,ja)1d(ja,ja,da)
    ===》分别推出四种结论:1a(da代表是,ja代表否) 1b(da代表是,ja代表否,且C是任意) 1c(ja代表是,da代表否) 1d(ja代表是,da代表否且C是任意)

    小结:无论哪种结果da与ja已经明确意思。所以假设da代表是继续推论1a和1b,1c和1d以此类推不再重复。

    第二问:
    情况1b:C是任意么?
    得到唯一回答:2a(da,ja)===》得出A是真实,B是虚伪【完毕】

    情况1a:da代表是么?
    得到回答:
    2b(da,ja,da) ===》B是虚伪
    2c(da,ja,ja)===》A是真实
    第三问:
    情况2b:指着A问B,他是真实么?
    得到两种回答:
    3a(da))===》得出A是任意,C是真实【完毕】
    3b(ja)===》得出A是真实,C是任意【完毕】

  12. Izual_Yang
    @5 years ago
    1703595

    @shuesiki:
    那么普通人秒杀高手大师和大神,因为普通人会先拿几个特例试试看,看这个问题是否超出自己的能力。

  13. 圣诞老公公
    @5 years ago
    1703587

    答案都看不懂。

  14. 强迫症患者_
    @5 years ago
    1703229

    直接看答案。= =

  15. 佚名十九
    @5 years ago
    1703193

    看了题目说是要花我一上午时间,所以果断戳答案,瞟一眼,算了,直接看以上评论,顿时豁然开朗·····

  16. calayanrail
    @5 years ago
    1703167

    问A:你会用你语言里代表“不”的词语回答这个问题吗?
    如果A是“真实”,A就会陷入悖论而爆掉
    然后继续问B第二个问题:你会用你语言里代表“是”的词语回答这个问题吗?
    如果B是“谎言”,B也会陷入悖论头爆掉。如果B没爆掉,那么B就是“随机”。
    于是我们最少只要两个问题就可能知道三神的身份了。但是我很贱,我贱贱的笑着问C,也就是“谎言”:你会用你语言里代表“是”的词语回答这个问题吗?只见“谎言”张大了嘴巴,两眼噙着泪花,“砰”的一声爆成了一股青烟。

    回到第一个问题之后
    如果A没爆掉
    继续问A第二个问题:你会用你语言里代表“是”的词语回答这个问题吗?
    如果A是“谎言”,A会爆掉
    然后问B:你会用你语言里代表“不”的词语回答这个问题吗?
    如果B爆掉了,B就是“真实”,反之则是“随机”

    回到之前第二个问题之后
    如果A还没爆掉,那么A是“随机”
    然后问B:你会用你语言里代表“不”的词语回答这个问题吗?
    如果B爆掉了,B是“真实”,反之则是“谎言”

    于是以平均一个神的神格毁灭为代价,我们只要三个问题就可以知道ABC分别是什么神啦!

    曾几何时宇宙由“真实”,“谎言”和“随机”三神共同统治。就这样137亿年过去了,在银河系第二旋臂上一颗G级恒星的第三颗行星上进化出了一种叫智人的贱贱的生物。有一天他们当中一个叫George Boolos的提出了一个号称史上最困难的逻辑问题。无数英雄,甚至包括Boolos自己,都倒在了解答这个问题的路上。终于有一天,Rabern两兄弟发现了问题的解法,顺便把“真实”和“谎言”的都爆掉了,只剩下“随机”统治三界。啊啊啊这就是为什么我们的世界是混沌的。

    改编自解法第4段:Exploding god-heads

    [11] XX [3] 回复 [0]
  17. Micheal_mi
    @5 years ago
    1702661

    我是直接看的答案,但是,我只看懂了文字……

  18. 1702495

    看了Rabern and Rabern 的解答,我艹,完美破解da ja的語言障礙啊,無敵了啊。

  19. 仙儿哥
    @5 years ago
    1702485

    一个问题就搞定。“请问你幸福么?”

  20. 莉莉丝
    @5 years ago
    1702357

    大晚上的坚决不浪费脑细胞

  21. 梅川酷子
    @5 years ago
    1702257

    看帖子之后从直接弃权题目看答案,变成直接弃权答案…..太长了。

  22. zzzzzzzzz
    @5 years ago
    1702189

    ddd dejav uuuuuu

  23. 你们感受一下
    @5 years ago
    1702117

    维基百科给出的答案是问了3个人两个不同的问题,我琢磨了一下午,只需问3个人相同的问题就可以解答是什么水平?当然借鉴他的了“内嵌问题引理”这个imba玩意儿。。。

  24. 双子
    @5 years ago
    1702087

    海龟汤??

  25. 姑苏城外伦敦塔
    @5 years ago
    1702005

    劳资花5分钟算出图上的算术,你却告诉我不是这个。。。

  26. martius
    @5 years ago
    1701971

    @ikarus: 你连题目都没看明白,一次只能问一位神

  27. 山萝卜
    @5 years ago
    1701969

    问每个神“你停止打你老婆了吗”

  28. ikarus
    @5 years ago
    1701913

    第一个问题:对三个神问 “你是真实么?”
    真实和虚伪都会说”是” 任意回答未知(未知若回答”否” 则第一个问题便能确定出任意之神 我们先假设任意也回答”是” 加大问题难度)
    但是已经可以从中确定”da”和”ja”哪个代表”是” 这里假设两位神明的回答都是”da” 得到”da”代表”是”

    第二个问题:对三位神问 “1+1=2么?”真实回答”是” 虚伪回答”否” 由于任意回答未知,这里将会有两种情况
    1:任意若回答”是” 则可以判断三位中回答”否”的是虚伪之神
    2:若任意回答”否” 则可以判断三位中回答”是”的是真实之神

    第三个问题:根据上面的两种情况而定(三位神标号为a b c)
    1:已找出虚伪之神(a) 问a:”b是任意之神么?” 若虚伪之神回答”是” 则b为真实之神,c为任意之神 若回答”否” 则b为任意之神
    2:已找出真实之神(a) 问a:”b是任意之神么?” 若真实之神回答”是” 则b为任意之神,c为虚伪之神 若回答”否” 则b为虚伪之神

    [5] XX [16] 回复 [0]
  29. sanders
    @5 years ago
    1701867

    问问他们: “你妈知道你是同性恋吗?”

  30. shuesiki
    @5 years ago
    1701823

    解答要问什么问题,那叫算法。
    解答至少需要问多少条问题才能够获得三个神的身份,那叫算法复杂度。
    解答至少需要问多少条问题才能够获得三个神的身份,并找出在最少情况下的问法,那叫做最优算法。

    找出算法的人,是高手。
    分析出算法限制以及复杂度的人,叫做大师。
    找出最优算法的人,叫做大神。

  31. zero1386
    @5 years ago
    1701779

    神的力量果然是无穷的,我还没看答案,不过 愉悦 啊
    第一问’下一位神是否回答da‘
    第二问’上一位神是否回答ja‘
    第三问’第二位神回答为何?‘

  32. Hybrid
    @5 years ago
    1701715

    我了个去 技术贴啊

  33. Gothazod
    @5 years ago
    1701711

    @Silver 不是Q牛逼,是那个E牛逼

  34. 大菜
    @5 years ago
    1701701

    中文版这么也打不开。求解释。。

[2] 1 »

发表评论


24H最赞