最简单而又最困难谜题(解决最难逻辑谜题)

有史以来最难的逻辑谜题是由逻辑学家 Raymond Smullyan 和 John McCarthy 提出的,此谜题在20世纪90年代就已闻名于世。

想象一下这里有三位信使,分别为True, False,Random。其中True总说真话,False总说假话,Random时真时假。你的任务是通过询问他们是/否的问题来确认三者的身份。但有一个额外的难题:信使们拥有自己神秘的语言,他们的回答会是“DA” / “BAL”,但你并不得知那个代表“YES”,哪个又代表着“NO”。

最简单而又最困难谜题(解决最难逻辑谜题)(1)

令人惊讶,其实我们只需三个问题就足以解开这个谜。在你开始思考之前,你需要事前了解三件事:

  • Random是通过秘密抛掷硬币来决定自己说真话还是谎言;
  • 你可以向他们三者提出任何是/不是的问题;
  • 你不需要一次性问完所有问题。你可以根据上轮答案随时调整询问你的下一轮问题以及下一位回答者。

如果你此刻绞尽脑汁,请不要绝望,毕竟它可是被誉为有史以来最难的逻辑谜题。解决这个问题通常的思路是:通过询问第一个问题,您需要找出非Random身份的信使 X。接着你再问X两个问题,第二个问题用来确定X是True还是False,第三个问题确定另外两位的身份。

当且仅当

这个方案使用了逻辑中当且仅当的概念:给定两个命题A、B,命题“当且仅当A,B”为真,意思是“A和B都为真或都为假”,否则命题为假。(本文的当且仅当是数学中逻辑关系,可能我们自己理解的因果关系略有偏颇,不过不要担心,请记住这个逻辑门关系来阅读本文),此逻辑举例说明:

当且仅当月亮是奶酪做的时,2 2=4,该命题为假。因为两个命题一个为真,一个为假。

而当且仅当月亮是奶酪做的时,2 2=5,该命题为真。因为这两个命题均为假。

最简单而又最困难谜题(解决最难逻辑谜题)(2)

月亮不是奶酪做的

“当且仅当”是“异或”的否定,你可以在此网址仔细阅读:https://plus.maths.org/content/os/issue36/features/nishiyama/index

从简单开始

现在我们回到最开始的谜题并做一个简化:假设DA代表“YES”,BAL代表“NO”。

首先,假设您已经向某个信使O提出了第一个问题,该信使O已经确定了X不是Random。你能想出一个简单的问题来揭示X是谁吗? 再接着,你能不能再提问X一个简单的问题来揭示另外两位信使的身份?

READING

以下是答案

为了判断X是True还是False,你只需问一个你已经知道答案的问题,例如: 2加2等于4吗?

要找出另外两个的身份,你可以这样问X:这个信使(指着你问的第一个信使O)是Random吗?

因为你已知道X是True或是False,你就可以确定你指着问的第一个信使O是否是Random。通过排除,您也可以识别出第三位的身份。

第一个问题

我们还是假设DA是“YES”,BAL是“NO”(稍后我们再讨论语言问题),我们先关注需要提问的第一个至关重要的问题,也是最困难的问题。随便找一个信使O问:

当且仅当这个信使(你指向一个信使,称之为 P)是Random,你是True吗?

如果您从O得到的答案是“是”且O为True,则P必是Random。因为当且仅当规定只要两部分均为真,或均为假,则为真;如果答案为“是”且O为False,则真实的答案应该为“否”,命题“当且仅当P为Random时O为True”为假。由于第一部分“ O为True”为假,因此第二部分“ P身份为Random”一定为真。

所以无论O是True还是False,答案“是”都告诉我们信使P的身份是Random,这意味着第三个信使,称为Q,不是Random。

如果O是Random,答案“是”告诉我们什么? 它不能确定地告诉我们P是什么,但这无关紧要。在这种情况下,因为O是Random,第三个信使 Q肯定不是Random。

综上所述,如果答案是“是”,那么我们可以肯定地说,无论O是什么,第三个信使Q肯定不是Random。

如果O的回答是“否”呢? 如果O为True,这就意味着P不是Random;如果O为False,那么正确答案应该为“是”,这个命题为真命题。则因为命题的第一部分为假,则命题的第二部分“P是Random”在这种情况下必然为假命题,即“P不是Random”。

所以无论O是True还是False,答案为“否”就告诉我们P不是Random。

如果O是Random,答案“否”会告诉我们什么? 它告诉我们P不是Random,因为O已是Random。

综上所述,答案“否”告诉我们,无论O是什么,P都不是Random。

在这两种情况下,无论O的答案是“是”还是“否”,我们都能确定其中一个信使不是Random的身份。如果O的答案是“是”,那么信使Q不是Random。如果O的答案是“否”,那么信使P就不是Random。这就达到了找出非Random身份的信使X的目的。我们现在可以按照步骤进行另外两个问题,进而解开谜题。下面的图表说明了我们将提问的三个问题以及各种答案。

最简单而又最困难谜题(解决最难逻辑谜题)(3)

该图列举了三个问题的各种答案。其中T代表True,F代表False,R代表Random。

注意,当且仅当的作用是在并不知道O是True/False/Random的情况下,从O的答案中获得确定性信息。

DA 和BAL

让我们来思考最初的谜题-------你并不知道DA和BAL的意思。因此我们需要引入深一层“当且仅当”,即通过在这三个问题的最后加上“当且仅当DA表示‘YES’”,我们可以把答案DA解释为对原问题的肯定答案,把答案BAL解释为对原问题的否定答案。下一节中,我们将举例说明它,现在我们将陈述这个谜题通常的解法。

首先选择一个信使O并问它:“当且仅当P是Random,当且仅当DA表示“YES”,你是True吗?”

当这两个命题“当且仅当P是Random,O是True” 和 “ DA代表‘YES’”同时为真或同时为假时,这个命题为真。

和以前一样,这个问题将识别出非Random身份的信使 X。然后,你再问X:“当且仅当DA代表‘YES’”,2 2=4吗?”

据此你将会判断出X是“True”还是“False”;

最后你再问X:“当且仅当DA代表‘YES’,O是Random吗? ”

和之前一样,因为你已经知道X的身份,所以由此你将会判断出O的身份,谜题解开!

真的吗?

为了证明可行,我们一起看一下最后一个问题。至此,我们已经知道X是True还是False了。

当X身份是True

你问X:“当且仅当DA代表‘YES’,O是Random吗?”

1.如果X回答DA,同时DA代表‘YES’,那么O是Random;如果DA代表‘NO’,那么O也是Random。这是因为:“DA代表‘YES’”是假命题时,那么X回答“DA”,代表在说‘NO’,则命题“O是Random”为真;

2.如果X回答BAL,同时BAL代表‘YES’,那么O不是Random。这是因为:“DA代表YES”是假命题时,既然X回答BAL,那么代表在说“YES”,那么“O是Random”必然是假命题。

正如我们上述所讨论的那样,如果X身份是True,那么X回答“DA”相当于在告诉我们“O的身份是Random”,而回答“BAL”相当于在告诉我们“O的身份不是Random”。

当X身份是False

与上同理,X回答“DA”相当于在告诉我们“O的身份不是Random”,而回答“BAL”相当于在告诉我们“O的身份是Random”。

总结一下,我们可以根据X的答案从而判断出O的身份是否是Random,而并不需要得知DA和BAL谁代表“YES”,谁代表“NO”。

这也就说明了,通过第一个问题的答案可确定一个非Random身份的X,由第二个问题的答案确定X为True 或是False,即使你并不知道DA和BAL 谁是YES谁是NO。谜底揭开~

作者简介

Antonella Perucca是卢森堡大学数论教授。她是数论研究人员,并举办过多场数学展览。想了解更多信息,可以浏览她的网页 http://www.antonellaperucca.net/

Author

最简单而又最困难谜题(解决最难逻辑谜题)(4)

文 / Antonella Perucca

翻译及排版 / Hurricane

校对 / 心月

原标题:True?False?Random?

来源:中科院高能所

编辑:观山不易、yrLewis

,

免责声明:本文仅代表文章作者的个人观点,与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺,请读者仅作参考,并自行核实相关内容。文章投诉邮箱:anhduc.ph@yahoo.com

    分享
    投诉
    首页