挑战逻辑极限！三个“史上最难”数学谜题，揭示思维陷阱，锻炼逻辑能力。附赠趣味数学书籍推荐！
原文标题：史上最难的数学逻辑谜题：这才是数学思维能力的最强体现！
原文作者：图灵编辑部
冷月清谈：
怜星夜思：
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篇精彩的文章。即使你不喜欢数学，也会为本书的精彩所倾倒。
这是一本标新立异的趣味数学书。每一个读过的人都会被深深吸引。这是一个热爱思考的年轻人积攒的让人一读就欲罢不能的趣味书。