挑战你的逻辑极限:史上最难数学谜题解析

挑战逻辑极限!三个“史上最难”数学谜题,揭示思维陷阱,锻炼逻辑能力。附赠趣味数学书籍推荐!

原文标题:史上最难的数学逻辑谜题:这才是数学思维能力的最强体现!

原文作者:图灵编辑部

冷月清谈:

本文精选了三个极具挑战性的逻辑谜题,旨在考察和提升读者的数学思维能力。第一个谜题通过反证法的漏洞,揭示了Berry悖论中“系统之内”和“系统之外”的区别。第二个谜题探讨了“共识”在逻辑推理中的重要性,并通过蓝眼睛岛问题、短信确认问题等生动案例进行阐述。第三个谜题是“史上最难的逻辑谜题”,要求在有限次数内识别出三台机器的身份,解答过程巧妙地运用了问题嵌套的技巧。文章还推荐了两本数学趣味读物,鼓励读者在数学的世界里不断探索和思考。

怜星夜思:

1、在“蓝眼睛岛”问题中,如果大法师说的是“岛上至少有两个人是蓝眼睛”,结果会怎样?推理过程会发生什么变化?
2、文章中提到的“共识”概念在现实生活中还有哪些应用?除了面对面交流和打电话,还有其他方法可以快速达成共识吗?
3、在“真理、谬误、随机”机器问题中,如果只能提问两次,有可能找出“真理”机器吗?如果不能,有什么理由?

原文内容

大概很多人都知道学好数学可以培养人的思维能力,而这种能力或许是比较模糊的说法,更为直观的能力体现之一则是逻辑能力。


逻辑性,是数学最为显著的特征。每一个结论的得出,都需要有条不紊地通过推导和证明。


你的逻辑性如何,不妨来试试下面的两个“史上最难的逻辑谜题”。(附赠一个开胃的小菜)

图书 | 《浴缸里的惊叹:256道让你恍然大悟的趣题》

作者:顾森


01


有一些正整数虽然很大,甚至超过了20位,但仍然可以用20个或更少的汉字表达出来。例如,100 000 000 000 000 000 000 000可以表达为“一后面二十三个零”,157 952 079 428 395 476 360 490 147 277 859 375可以表达为“前二十七个正奇数之积”。下面,我要证明一个非常惊人的结论:事实上,所有的正整数都可以用20个以内的汉字表达出来!


证明的基本思路是用反证法。假设存在某些不能在20个汉字以内表达的正整数,那么这里面一定有一个最小的不能在20个汉字以内表达的正整数,而这个数已经被我们用“最小的不能在二十个汉字以内表达的正整数”表达出来了,矛盾。因此,我们的假设是错误的。由此可知,所有的正整数都可以用20个以内的汉字表达出来。


我的证明过程正确吗?如果不正确,问题出在哪儿?

所有的正整数都可以用20个以内的汉字表达出来,这个结论明显是错的——用20个或者更少的汉字组成一个句子,总的方案数量是有限的;而正整数是无限多的,它们不可能都有与之对应的句子。所以,我的“证明”过程当中一定有某些非常隐蔽的问题。关键是,这个问题在哪儿呢?如果我们对正整数的表达方法做一个细致的分析,问题就逐渐暴露出来了。

什么叫做用若干个汉字表达一个数?这里面可能会涉及很多问题,比如有些句子根本就不合语法,比如有些句子根本就不是在表达一个数,比如有些句子的意思可能存在模糊或者有歧义的现象,比如有些句子涉及太多技术问题以至于很难算出它在表达哪个数。不过,这些细节问题我们都不管。我们假设有一台超级强大的机器,每次我们可以往里面输入一个汉语句子(但不能超过20个汉字),机器就可以根据内置的一系列复杂规则,自动判断这个句子是否合法地表达了一个正整数,如果是的话,它还能具体地给出这个数的值。这台假想的机器就明确了汉字“表达”数字的具体含义。

所以,有些数是这台机器能输出的,有些数是这台机器不能输出的。当然,这里面会有一个最小的这台机器不能输出的数。而且,“最小的这台机器不能输出的数”本身就不足20个字,是可以输进这台机器的。那么,把这句话输入机器,会得到什么呢?不要带有任何期望——机器会告诉我们,这句话并不能表达一个数。机器读到这句话的第一反应将会是:啊,机器?什么机器?我们站在这台机器之外,能够弄明白“最小的这台机器不能输出的数”是什么意思,但这句话在机器内部是不能被理解的。

类似地,“这个数已经被我们用‘最小的不能在二十个汉字以内表达的正整数’表达出来了”,在这句话里,里面那一层的“表达”和外面那一层的“表达”有着不同的内涵和外延。我们不妨把里面那一个表达记作“表达1”,把外面那一个表达记作“表达2”。整句话就成了“这个数已经被我们用‘最小的不能在二十个汉字以内表达1的正整数’表达2出来了”。表达1和表达2有什么区别呢?至少有这么一个区别:表达2的规则里可以使用表达1这个概念,但表达1的规则里显然不能使用表达1这个概念。由于表达2更强大一些,因此最小的不能用20个以内的汉字表达1的正整数,完全有可能用20个以内的汉字表达2出来,这并没有矛盾。

这个有趣的逻辑困惑叫做Berry悖论,它是由伯特兰·罗素(Bertrand Russell)在 1908年American Journal of Mathematics 的一篇论文当中提出来的。根据论文脚注中的描述,这个逻辑困惑是牛津大学的图书馆管理员G. G. Berry想出来的,于是就有了Berry悖论这个名字。Berry悖论揭示了数理逻辑中一个至关重要的概念,即“系统之内”和“系统之外”的区别。

伯特兰·罗素是20世纪英国著名的数学家,他对数学底层的逻辑系统有过很多深刻的研究。1910年到1913年期间,他和阿尔弗雷德·怀特海(Alfred North Whitehead)合著了《数学原理》(Principia Mathematica),这可以称得上是史无前例的数学巨作。两人花了总共三卷的篇幅,从最底层的公理出发,用最严谨的逻辑,逐步推出各种各样的数学结论,搭建起整座数学大厦。全书第一卷第379页正中间的一小段话成为了经典中的经典:“定义算术加法之后,根据这一命题便可得出,1+1=2。”

罗素这人简直就是一神人,举个例子吧,他曾经获得过诺贝尔奖。等等,诺贝尔奖不是没有数学奖吗?其实,罗素获得的是诺贝尔文学奖。罗素不但是一个数学家,还是一个哲学家,他对历史、政治、文学都抱有极大的兴趣。很难想象,《数学原理》和《社会重建原则》(Principles of Social Reconstruction)竟然是罗素在同一时期创作的作品。1950年,他因“多样且重要的作品,持续不断地追求人道主义理想和思想自由”获得了诺贝尔文学奖。

02


某座岛上有200个人,其中100个人的眼睛是蓝色的,另外100个人的眼睛是棕色的。所有人都不知道自己眼睛的颜色,也没法看到自己眼睛的颜色。他们可以通过观察别人的眼睛颜色,来推断自己的眼睛颜色;除此之外,他们之间不能有任何形式的交流。每天午夜都会有一艘渡船停在岛边,所有推出自己眼睛颜色的人都必须离开这座岛。所有人都是无限聪明的,只要他们能推出来的东西,他们一定能推出来。岛上所有人都非常清楚地知道上面这些条件和规则。


有一天,一位大法师来到了岛上。他把岛上所有人都叫来,然后向所有人宣布了一个消息:岛上至少有一个人是蓝眼睛。


接下来的每一个午夜里,都会有哪些人离开这座岛?

答案:从第1个午夜到第99个午夜,没有任何人离开这座岛;到第100个午夜,所有100个蓝眼睛将会同时离开。

为什么?大家不妨先这样想:什么情况下第一天就会有人离开这座岛?很简单。假如岛上只有一个人是蓝眼睛,那么当他听说岛上至少有一个蓝眼睛的人之后,他就知道了自己一定就是蓝眼睛,因为他看到的其他所有人都是棕色的眼睛。因而,当天夜里他就会离开这座岛。好了,如果岛上只有两个蓝眼睛的人呢?他们在第一天都无法立即推出自己是蓝眼睛,但在第二天,每个人都发现对方还在,就知道自己一定是蓝眼睛了。这是因为,每个人都会这么想:如果我不是蓝眼睛,那么对方昨天就会意识到他是蓝眼睛,对方昨天夜里就应该消失,然而今天竟然还在这儿,说明我也是蓝眼睛。最后,这两个人将会在第二天夜里一并消失。

类似地,如果岛上有三个蓝眼睛的人,那么每个人到了第三天都发现另外两个人还没走,便能很快推出,这一定是因为自己是蓝眼睛。所以,这三个蓝眼睛的人将会在第三个午夜集体离开。不断地这样推下去,最终便会得出,如果岛上有100个蓝眼睛的人,那么每个人都会在第100天意识到自己是蓝眼睛,于是他们将会在第100个午夜集体离开。

很多人都会对这段解释非常满意,然而细心的朋友却会发现一个问题:在大法师出现之前,每个人都能看见99个蓝眼睛的人,因此每个人都知道“岛上至少有一个人是蓝眼睛”这件事情。那么,大法师的出现究竟有什么用呢?这是一个很好的问题。它的答案是:大法师的行为,让“岛上至少有一个人是蓝眼睛”的消息成为了共识。

在生活当中,我们经常会遇到与共识有关的问题。让我们来看这么一段故事。A、B两人有事需要面谈,他们要用短信的方式约定明天的见面时间和地点。不过,两人的时间都非常宝贵,只有确信对方能够出席时,自己才会到场。A给B发短信说:“我们明天10:00在西直门地铁站见吧。”不过,短信发丢了是常有的事情。为了确信B得知了此消息,A补充了一句:“收到请回复。”B收到了之后,立即回复:“已收到,明天10:00不见不散。”不过,B也有他自己的担忧:A不是只在确认我要去了之后才会去吗?万一他没有收到我的确认短信,届时没有到场让我白等一中午怎么办?因此B也附了一句:“收到此确认信请回复。”A收到确认信之后,自然会回复“收到确认信”。但A又产生了新的顾虑:如果B没收到我的回复,一定会担心我因为没收到他的回复而不去了,那他会不会也就因此不去了呢?为了确保B收到了回复,A也在短信末尾加上了“收到请回复”。这个过程继续下去,显然就会没完没了。其结果是,A、B两人一直在确认对方的信息,但却始终无法达成这么一个共识:“我们都将在明天10:00到达西直门地铁站”。

有的人或许会说,那还不简单,A给B打个电话不就行了吗?在生活当中,这的确是上述困境的一个最佳解决办法。有意思的问题出来了:打电话和发短信有什么区别,使得两人一下就把问题给解决了?主要原因可能是,打电话是“在线”的,而发短信是“离线”的。在打电话时,每个人都能确定对方在听着,也能确定对方确定自己在听着,等等,因此两人说的任何一句话,都将会立即成为共识:不但我知道了,而且我知道你知道了,而且我知道你知道我知道了……

大法师当众宣布“岛上至少有一个人是蓝眼睛”,就是让所有人都知道这一点,并且让所有人都知道所有人都知道这一点,并且像这样无限嵌套下去。这就叫做某条消息成为大家的共识。让我们来看一下,如果这个消息并没有成为共识,事情又会怎样。

为了简单起见,我们还是假定岛上只有两个人是蓝眼睛。这两个人都能看见对方是蓝眼睛,因而他们都知道“岛上至少有一个人是蓝眼睛”。但是,由于法师没有出现,因此他俩都不知道,对方是否知道“岛上有蓝眼睛”这件事。所以,到了第二天的时候,之前的推理就无法进行下去了——每个人心里都会想,对方没有离开完全有可能是因为对方不知道“岛上有蓝眼睛”这件事。

类似地,如果岛上有三个人是蓝眼睛,那么除非他们都知道,所有人都知道所有人都知道了“岛上有蓝眼睛”这件事,否则第三天的推理是不成立的——到了第三天,会有人觉得,那两个人没走仅仅是因为他们不知道对方也知道“岛上有蓝眼睛”这件事罢了。继续扩展到100个蓝眼睛的情形,你会发现,“互相知道”必须得嵌套100层,才能让所有推理顺利进行下去。

实际上,我们的题目条件也是不完整的。“岛上的所有人都非常清楚地知道上面这些条件和规则”这句话应该改为“上面这些条件和规则是岛上所有人的共识”,或者说“岛上所有人都知道上面这些条件和规则,并且所有人都知道所有人都知道,等等等等”。如果没有这个条件,刚才的推理也是不成立的。比方说,虽然所有人都是无限聪明的,但是如果大家不知道别人也是无限聪明的,或者大家不知道大家知道别人也是无限聪明的,推理也会因为“昨晚他没走仅仅是因为他太笨了没推出来”之类的想法而被卡住。下一章的博弈问题当中,共识的概念也会起到很大的作用。

这是一道非常经典的问题,网络漫画网站XKCD把它称作是“世界上最难的逻辑谜题”。我至少见过这个问题的四种不同的版本。John Allen Paulos的Once Upon A Number里写过一个大女子主义村的故事:村子里有50个已婚妇女,每个妇女都不知道自己的男人是否有外遇,但却可以观察到其他妇女的男人是否有外遇。规定,只要哪个妇女推出了自己的男人有外遇,当晚她就必须把自己的男人杀死。有一天,村子里来了一位女族长。女族长宣布,岛上至少有一个妇女,他的男人有外遇。实际上,每个妇女的男人都有外遇。那么最后究竟会发生什么呢?村子里的人将会度过49个平静的晚上,到第50天则会出现彻彻底底的大屠杀。

另一个与疯狗有关的版本也大致如此:村子里每个人都养了一条狗,每个人都不知道自己的狗是不是疯了,但都可以观察到别人家的狗是不是疯狗。只要推出自己的狗是疯的,当天晚上就必须用枪把它杀死。有一天,村里来了一个人,宣布了至少有一条疯狗的消息,然后前2天平安无事,第3天夜里出现了一阵枪响,问村子里实际上有多少疯狗?答案是,3条。

最后还有一个戴帽子的版本。老师给5个小孩儿每个人头上都戴了一顶黑帽子,然后告诉大家,至少有一个人头上戴着的是黑色的帽子。接下来,老师向大家提问:“知道自己戴着黑帽子的请举手”,连问4次没有反应,到了第5次则齐刷刷地举手。有的地方把“戴着黑帽子”换成“额头上点了一个墨点”,然后老师让大家推测自己额头上是否有墨点。这本质上也是一样的。

03


有三台机器A、B、C,它们分别叫做“真理”、“谬误”和“随机”(但你不知道谁是谁),其中“真理”永远说真话,“谬误”永远说假话,“随机”则会无视问题内容,随机作答。每次你可以向其中一台机器提问,提出的问题只能是是非问句的形式。这台机器将会用da和ja来回答你,这两个词一个表示“是”,一个表示“否”,但你也不知道哪个词表示哪个意思。你的任务是用三次提问的机会辨别出A、B、C这三台机器各自的身份。


需要注意的是,你可以向同一台机器多次提问,也就是说,这三个问题不一定是分别提给这三台机器的。另外,每一次都是向谁提出什么问题,这并不需要一开始就完全定下来,后面的提问内容和提问对象可以根据前面得到的回答而“随机应变”。“随机”的行为应该视作一枚公平的硬币:每次回答问题时,他都有50%的概率说da,有50%的概率说ja。

估计大家见过类似的题目,只不过没这么变态而已。有一类题目叫做“骑士与无赖”(Knights and Knaves),基本假设就是骑士永远说真话,无赖永远说假话,你需要向他们问一些问题,从而获取某些正确的信息。其中一个经典的问题就是,有一个岔路口,其中一条路通往天堂,另外一条路通往地狱,但是你不知道哪条路通往哪里。每条路上都站着一个人,一个是骑士,一个是无赖,但是你也不知道谁是谁。你怎样向他们中的一个人提出一个是非问题,从而判断出哪条路是通往天堂的路?

答案是,随便问一个人:另一个人是否会告诉我你这条路是去往天堂的?如果这个人回答“不会”,那么这有两种情况:这个人是骑士,他在如实地警告你,另一个人会骗你说这条路不会通往天堂;或者这个人是无赖,他骗你说,另一个人不会告诉你这条路通往天堂。总之,这条路就是通往天堂的;如果这个人回答“会”,那么这有两种情况:这个人是骑士,他在如实地警告你,另一个人会骗你说这条路就是通往天堂的;或者这个人是无赖,他骗你说,另一个人会告诉你这条路通往天堂。总之,这条路就是通往地狱的。

这已经是非常困难的逻辑问题了,但显然,它还是没有三台机器的问题困难。在维基百科上有一个条目叫做“史上最难的逻辑谜题”(The Hardest Logic Puzzle Ever),说的就是这个问题。根据维基百科的描述,这个问题是由美国逻辑学家 George Boolos在1996年出版的The Harvard Review of Philosophy 一书中提出的。

这个问题的解法有很多,下面是其中一种比较巧妙的解法。我们需要用到一个非常无敌的技巧:对于任意一个是非问题P(比如说“A是‘随机’吗”),如果你想知道它是对的还是错的,那么就向“真理”或者“谬误”中的其中一个提问:“如果我问你P,你会回答ja吗?”只要得到的回答是ja,就说明P是正确的;只要得到的回答是da,就说明P是错误的。为什么?要想证明这一点其实是很容易的,只需要分别考虑以下8种情况就可以了。

(1) 若P是正确的,问的是“真理”,ja表示“是”,则得到的回答是ja

(2) 若P是正确的,问的是“真理”,ja表示“否”,则得到的回答是ja

(3) 若P是正确的,问的是“谬误”,ja表示“是”,则得到的回答是ja

(4) 若P是正确的,问的是“谬误”,ja表示“否”,则得到的回答是ja

(5) 若P是错误的,问的是“真理”,ja表示“是”,则得到的回答是da

(6) 若P是错误的,问的是“真理”,ja表示“否”,则得到的回答是da

(7) 若P是错误的,问的是“谬误”,ja表示“是”,则得到的回答是da

(8) 若P是错误的,问的是“谬误”,ja表示“否”,则得到的回答是da

直观地想一想,道理也不复杂。先来看看“真理”吧。对于“如果有人问你P,你会怎么回答”这样的问题,“真理”的反应大致有4种:会回答“是”,不会回答“否”,会回答“否”,不会回答“是”。前两种情况都意味着,P是正确的;后两种情况都意味着,P是错误的。前两种情况其实属于同一种情况,即对于“你会回答ja吗”的答案就是ja;后两种情况其实也属于同一种情况,即对于“你会回答ja吗”的答案是da。总结起来就是,对于“如果我问你P,你会回答ja吗”这样的问题,回答ja就意味着P是正确的,回答da就意味着P是错误的。

那么“谬误”呢?最精妙的地方就在这里:我们巧妙地用了问题的嵌套,让“谬误”的行为和“真理”一样了。试想,如果“谬误”拿到了“如果有人问你P,你会回答ja吗”这样的问题,它会怎么办?它肯定会欺骗你,让你以为,如果真的有人问它P时,它会像乖孩子一样好好回答。它会阴笑着回答你,“嘿嘿,如果有人问我P,我会回答ja的”,或者“嘿嘿,如果有人问我P,我不会回答ja的”。在这一瞬间,它的思路就和“真理”一样了。

反复利用这种“问题嵌套”的技巧,我们就能迅速判断出A、B、C三者的身份了。首先,我们要用一次提问找出一台肯定不是“随机”的机器。为此,我们询问机器B:如果我问你“A是不是‘随机’”,你会回答ja吗?如果B回答ja,那么要么它自己就是“随机”,要么它是“真理”和“谬误”之一,其回答将表明A是“随机”。不管怎样,C都不是“随机”。如果B回答da,那么要么它自己就是“随机”,要么它是“真理”和“谬误”之一,其回答将表明A不是“随机”。不管怎样,A都不是“随机”。

第一步完成后,我们就找出了一台机器(有可能是A,有可能是C),它一定不是“随机”。然后就问它:如果我问你“你是不是‘真理’”,你会回答ja吗?它的回答将会直接告诉你它的身份。最后,继续问它:如果我问你“B是不是‘随机’”,你会回答ja吗?它的回答将会直接告诉你另外两台机器究竟谁是“随机”,从而揭晓所有机器的身份。

01

《浴缸里的惊叹:256道让你恍然大悟的趣题》

作者:浴缸里的惊叹:256道让你恍然大悟的趣题


《浴缸里的惊叹》源自阿基米德的那句“Eureka”,是那种苦思冥想后恍然大悟的奇妙感觉。本书精选自作者顾森十余年来精心收集的数学趣题,广泛包含了几何、组合、行程、数字、概率、逻辑、博弈、策略等诸多类别。其中既有小学奥数当中的经典题目,又有难题。多数题目都很简单,基本不需要繁复的计算或者艰深的专业知识,只需动脑或动手就可以想出答案,但想出所有答案也不是那么容易,有利于激发读者进一步探索数学问题的兴趣。


02

《思考的乐趣:Matrix67数学笔记》

作者:顾森

中科院院士张景中、汤涛联袂推荐


本书是一个疯狂数学爱好者的数学笔记,面向所有喜爱数学的读者。本书包括5部分内容,即生活中的数学、数学之美、几何的大厦、精妙的证明、思维的尺度,涉及48篇精彩的文章。即使你不喜欢数学,也会为本书的精彩所倾倒。


这是一本标新立异的趣味数学书。每一个读过的人都会被深深吸引。这是一个热爱思考的年轻人积攒的让人一读就欲罢不能的趣味书。

这种情况会使问题变得更复杂,需要考虑更多层级的推导,不过我选择直接躺平,太烧脑了!

这题有点意思,让我想想。如果大法师说“至少两人是蓝眼睛”,那么对于只有一个蓝眼睛的人来说,他看到的所有人都是棕色眼睛,就无法确定自己是不是蓝眼睛,所以第一天没人走。但如果有两个人是蓝眼睛,他们互相看到对方的蓝眼睛,都符合“至少两人是蓝眼睛”的条件,第二天他们就都能推出自己也是蓝眼睛,然后一起走了。

理论上来说,应该是不行的,信息量不够。排除法需要的信息量是大于解的数量的,两次提问能得到的信息撑死2bit,但是要区分三个机器,至少需要log3 bit的信息,所以信息量是不够的。

我觉得“共识”在团队合作中很重要啊,比如开会讨论方案,如果大家没有达成共识,后面执行起来肯定会出问题。现在很多项目管理工具都有在线协作功能,可以实时编辑文档、评论,也能帮助团队成员更好地理解彼此的想法,更快地达成共识。

共识在分布式系统领域非常重要,像区块链技术,就需要依赖共识算法来保证数据的一致性和安全性。除了面对面和打电话,一些即时通讯工具,如果能确保消息的可靠送达和已读状态,也能在一定程度上帮助快速达成共识。

想快速达成共识?简单粗暴的方法就是“投票”!少数服从多数,虽然不一定是最优解,但效率绝对高。

如果大法师说的是“岛上至少有两个人是蓝眼睛”,那么需要两天时间才能有人离开岛屿。岛上只有一个蓝眼睛的人,他第一天就会离开;岛上有两个蓝眼睛,他们第二天会离开…以此类推

我尝试分析了一下,两次提问要确定“真理”机器,必须在第一次提问后就能将范围缩小到只有“真理”和“谬误”两种可能,这样第二次提问才能奏效。但由于“随机”机器的存在,第一次提问的结果很可能是不确定的,所以我觉得理论上不可行。

两次提问找出“真理”机器?感觉不太可能。因为“随机”机器的存在,让问题变得复杂。第一次提问可能只能排除掉一台“随机”机器,但剩下两台机器的身份依然无法确定。除非运气爆棚,否则单凭两次提问很难锁定“真理”机器。