“善科”（http://www.mysanco.com/）是一个数学在线教育的网站，其中有一个问答馆，聚集了很多数学专家和爱好者。由于劈砖事件，有幸认识了场馆的总馆主香港浸会大学数学系讲座教授和理学院院长汤涛老师，并被邀请开设一个工程数学的馆。在各位专家和高手面前，本人亚历山大。果然，很快就有来踢馆的，抛出一道号称最难的逻辑题。先把题目列出供大家参考，有兴趣的可以先自己玩玩再看分析（至于是否如题目宣传的出自MIT未考证过）：

 

根据已故的麻省理工( MIT )哲学及逻辑家George Boolos，以下的趣味逻辑问题可算是全世界最难的一个。你可以解决这个难题吗？

 

有甲、乙、丙三个精灵，其中一个只说真话，另外一个只说假话。还有一个随机地决定何时说真话，何时说假话。你可以向这三个精灵发问三条是非题，而你的任务是从他们的答案找出谁说真话，谁说假话，谁是随机答话。这个难题困难的地方是这些精灵会以“Da”或“Ja”回答，但你并不知道它们的意思，只知道其中一个字代表“对”，另外一个字代表“错”。你应该问那三条问题呢？

 

见：
http://www.mysanco.com/wenda/index.php?class=discuss&action=question_item&questionid=973

 ----------------------------------------------------------------------------------------------------------------

一个搞笑的答案

看到这道题时正在等飞机，晚点已经是常事，于是开始思考这个问题打发时间。当时没有完全解答，但是很快想到一个搞笑的答案，于是搞笑回答了一下：

 

楼主公布答案前，我来搞笑下，一个问题先让真假两精灵崩溃，无言以对
问：你的回答意思将是“错”吧？
该问题只有不靠谱精灵敢回答，找出他下面就太简单了！大家继续发挥

 

其实当时考虑不周全，因为假话精灵不会有压力，对该问题他回答任何答案都可以。后来仔细一想，这个搞笑回答不无道理。因为情况确实会发生，不知道当时出题者是否忽略了这种情况。当这种问题被允许时，最少只需要问两个问题就可以了，而且可能不需要知道Da/Ja的具体含义。分析如下：

 

第一个问题问：你的回答意思将是“错”吧？

此时先看真话精灵不知道怎么回答。因为如果他回答“对”，那么他回答的意思就不是“错”，他说谎了；如果他回答“错”，那么他的回答应证了“你的回答意思将是“错””这一判断，他却判断为“错”，这跟他说真话的职责相悖。所以他只能选择沉默。

再看假话精灵，如果他回答“对”，则他的回答有悖“你的回答意思将是“错””这一判断，他说了谎，但这正是他的职责。反之，如果他回答“错”，则他应证了判断却给出相反的判断也旅行了自己的职责。

最后看不靠谱精灵，这里要分情况讨论下，因为根据题目他的职责是随机选择靠谱还是不靠谱的答案。这样，如果他需要先判断出答案的“对”“错”属性再随机选择，那么他会遇到跟真话精灵同样的困境而只有沉默。如果他不需要先判断，之需要提供一个随机的答案，那就简单，他只用随机提供一个答案。

第一个问题后的总结：如果只有一个精灵保持沉默，那他一定是真话精灵。如果有两个精灵保持沉默，发言的必然是假话精灵。

 

那么第2个问题只需要让第一轮被识别出的精灵（那个真话或者假话精灵）去指认剩下的那两个精灵就可以了，思路与下面的正规回答类似。但是此时Da/Ja的意义还不明确，需要做一些推断。假设真话精灵被识别出，那么可以问：（指着其中一个未识别出的精灵）他是假话精灵么？情况A：如果指的那个确实是假话精灵，被指的那个的答案必然与真话精灵的答案不一样。反之，如果被指的答案跟真话精灵一样，则被指的必然是不靠谱精灵 。情况B：如果被指的不是假话精灵（而是那个不靠谱的随机精灵），则答案跟真话精灵可能一样也可能不一样。但是此时可以参考第三个精灵。因为第3 精灵在这种情况下为假话精灵，所以他此时必须与真话精灵的不同，如果相同，被指的必为假话精灵。这样情况AB有一个交集，即：两个混淆的精灵的回答都与真话精灵不同。此时为最差情况，可能需要再多问一个问题。第３个提问的逻辑在下面正规回答里面讨论。当假话精灵被识别出来时，跟上面的假设是一个对称问题。不再讨论。

 

-------------------------------------------------------------------------------------------------------------------

以下提供一个正规的回答，这个回答应该才是出题者所期待的

 

上飞机前发了个搞笑答案。起飞后一直在思考这个问题，终有所获。问题虽小，但其解答过程很有趣。首先，看到题目可能很多童鞋被吓坏了，因为又是MIT又是号称最难的。其实，只要仔细分析，这个问题看着选择很多，其实解集非常小。

先说三个精灵，其实真假两个精灵无论回答什么，答案是确定性的，所以他们是靠谱精灵。另外一个随机回答的完全就是不靠谱，你别希望能从他身上得到什么。既然这样，干脆先忽略他，集中精神来区分真假两精灵就可以了。

然后说要问的问题。如果这个问题是个普遍的真理或者其逆命题(很多童鞋把功夫花这上面了)，真假两精灵的回答必然相左。一直问这样的 问题不会有什么新的结果。因为Da和Ja的意义不明。所以，肯定要利用相对真理，即回答根据两精灵的情况答案是不同的，自然这个问题最好的就是精灵的自我 或者对其他精灵的身份认同。例如“你是真精灵么？”这些问题会让真假两精灵的答案有两种：相同，或者相异。所以我们只需要先考虑所提出问题的期待答案是相 同或者相异就可以了。这样问题的解集就非常小，是个由“同”“异”构成的3元排列，如：{同同异，同异同，…}。解集大小只有2^3=8。够小吧？

最后，其实解集里面一些答案显然可以排除的，例如：同同同，异异同等等。另外，提问过程还可以充分利用对称性，排除或者避免去考察一些假设，因为是先找出真精灵和还是先找出假精灵并不重要。一个假设的对称假设只影响这种顺序。利用对称性，不用纠结过多的假设分支，尽快找到答案。

综上所述，这样一算下来，解集非常小只有：{同XX，异XX}了。

那么我们来考察第一个问题吧。我们需要通过此题获取尽量多的信息。这里只需考察期待答案是“同”还是“异”。显然，如果是“异”你什 么都得不到。所以只能是“同”，这样三个精灵回答里面必有2个相同（不管是Da或者Ja），相当于帮你投票了。此时票数多的Da/Ja对应的就是那个问题 的答案“对/错”。例如此时问：“你是真话精灵吧？”真假精灵都必然回答“对”。这样的问题还可以是否定答案的，如“你是假话精灵吧？”此时占优回答为 “错”。不再列举，总之，第一轮只能问“同”的问题，之后你就明白Da和Ja的含义了。注意此时解集缩小为{同异异，同异同，同同异}了。

接着考察第2个问题。此问题显然不能再为“同”了，因为这样无法区分出精灵来。所以必为“异”。这样，不靠谱精灵必然符合真假精灵其 中一个的答案。那个回答独树一帜的必然是真/假精灵。这个很容易判断，因为此时你已经知道Da和Ja的真实含义了。这个问题的可以是普遍真理或者其逆命 题，如：“1+1=2吧？”。这里可能产生很多情况，但是不靠谱精灵必附和其中一个靠谱精灵造成其所选答案占优。假设其附和了真精灵，那必然假精灵的回答 独树一帜而被识别出来。利用对称性，如果其符合假精灵，真精灵被识别出来。

此时到第3个问题了，此时的问题时如何区分出靠谱精灵和被他附和的那个精灵。这里需要点小技巧，因为无论你问什么问题，无论问多少 次，不靠谱的精灵都可以继续附和先前那个跟他身份混淆的精灵。所以此时两个被混淆精灵的答案完全没有参考价值。解决方案很简单：我们只能寄希望于那个已经 被识别出来的靠谱精灵。此时，如果再问你知道答案的问题，他的答案必然也是可以预测的，毫无意义。所以必须问一个你不知道答案的问题“被混淆的两个精灵 （假设为B和C）谁是真（或者假）精灵？”转换成一个判断题就是“B（C）是真（假）精灵吧？”因为被识别出的靠谱精灵的答案是可预知的，所以可以根据他 的判断来“指认”出被混淆的真（或者假精灵）了。问题解决！

附可能的解答一个：

1） 你是真精灵么？假设答案Da占优，则Da为“对”，如果Ja占优为对称问题，类似。

2） 1+1=2吧？假设不靠谱精灵附和真话精灵，则他们的答案都为“对”。此时假话精灵的答案必为“错”，从而暴露自己身份。类似，对称假设不再列举。

3） B为真话精灵么（此时假设混淆的两精灵为B和C）？此时只用看2）中暴露身份的假话精灵的答案，若为“错”，则B是真话精灵，反正不是。对称假设不再列举。

转载本文请联系原作者获取授权，同时请注明本文来自魏骁勇科学网博客。
链接地址：https://wap.sciencenet.cn/blog-805667-635497.html

上一篇：罗妙真
下一篇：我国早期的航模运动