最燒腦解密-三神謎題

放國慶長假放得腦袋整天昏昏沉沉的，來玩點燒腦小遊戲吧，最近複習了一下離散數學，來看看邏輯推理謎題-三神謎題的問題描述。

1996年，數學邏輯學家George Boolos（下圖）發表了一篇論文，描述了“有史以來最難的邏輯難題”，他將其歸因於邏輯學家Raymond Smullyan，我們首先來看一下問題的翻譯版本：

問題重述

“A、B、C三個神，按順序被稱爲True、False和Random。True總是說真話，False總是說假話，Random說真話還是假話完全是隨機的。你的任務是通過問三個問題來確定A、B和C的身份；每個問題都必須問一個神。神懂英語（你理解成懂中文也行），但會用他們自己的語言回答所有問題，其中“是”和“否”的單詞按某種順序是“da”和“ja”。你不知道哪個詞意味着哪個。” 你的目標是確定誰是真神(True)、誰是僞神（False，或者可以叫做假神）、誰是隨機神（Random）。

論文截圖來自MIT technology review

對於該謎題，George Boolos給出了一些約束：

• 允許一位神被問到了不止一個問題（有些神可能根本沒有被問到任何問題）。

• 第二個和第三個問題的內容和指向哪位神可以依賴於之前問題的答案（即可以根據第一個問題的答案再決定向哪位神問第二個問題、第二個問題的內容是什麼）。

• 可以認爲隨機神腦子裏有一枚（理想的）硬幣，隨機神在回答問題之前會先在腦中擲幣，然後根據擲幣結果決定自己是給出與真實情況相同的回答、還是給出與真實情況相反的回答。（也就是說即使三個問題都問隨機神，他可能也不會一直說真話或者一直說假話。）當被問及是非問題時，隨機神將回答da或者ja。

在觀看下面的分析之前，大家可以先想一下該如何提問？

簡化問題分析，如果沒有隨機神？

看完整個問題我們可以稍微梳理一下，如果沒有隨機神，那麼問題可以怎麼分析呢？考慮一個很常見的邏輯題，如果你走到一條岔路上，前面遇到兩個人，一個人永遠說真話，一個人永遠說假話，你並不知道誰說真話誰說假話，只許問其中一個人一句話，該如何發問？

這裏可以運用一個不太常見的問題，可以叫做嵌入式問題引理。我們隨便問一個人：你知道另一個人會把哪條路指爲正確的路嗎？對方回答後，你選擇答案的另一條路即可。分析如下：

假設A身後的路是真的說真話，你問他:你覺得我問B：你身後的路是不是真的，它會怎麼回答我？

這時候A如果說：B會回答真的

注意A說的真話，那麼b身後的路就會是假的。

同理：假設A說的假話是假的路，問A:你覺得我問B：你身後的路是不是真的，它會怎麼回答我

A說：B會回答假的。

那麼B路就是真的。所以不管你怎麼問，問誰，都會得到相反的答案，這時候你只要走相反的就行了

回到三神問題本身，作者Boolos的解法

其實Boolos 在論文中發表的解決方案並沒有使用嵌入問題的方法，他提出的問題是：“當且僅當 B 是隨機神時，當且僅當你是真神時，da 是否意味着是？”，就是說Boolos 使用了兩個條件假設，側重於通過複雜的問題找到 True 或 False。這個複雜問題也很有意思，相當於你說“當且僅當羅馬在俄羅斯，月亮是由山東大學制成的”，那麼你就做出了正確的陳述，因爲它的兩部分都是錯誤的。“當且僅當羅馬在意大利時，月亮沒有空氣”這句話也是正確的，因爲它的兩個部分都是正確的。

邏輯推理過程大概是這樣的(我自己推的，可能有錯誤，歡迎指正)：

一、分析第一階段提問

首先向神 A 提問“當且僅當 B 是隨機的，‘da’是否意味着你是真的？”，這個問題的巧妙之處在於無論 A 的回答是什麼，都能得到有用的信息：

1. 如果 A 是真或假，得到答案“da”： 可以推斷出 B 是隨機神。進而知道 C 要麼是真，要麼是假。

2. 如果 A 是真或假，得到答案“ja”： 可知 B 不是隨機神。 所以 B 要麼是真，要麼是 False。

3. 如果 A 是隨機，得到答案“da”： 能推出 C 不是隨機神（同時 B 也不是隨機神，但此時 B 的情況無關緊要）。 -因此 C 要麼是真，要麼是假。

4. 如果 A 是隨機，得到答案“ja”： B 不是隨機神（C 也不是隨機神，同樣此時 C 的情況無關緊要）。 所以 B 要麼是真，要麼是假。

總之，“da”的回答確保 C 不是隨機神，“ja”的回答對 B 有同樣的確定作用，即能確定 B 不是隨機神。

二、分析第二階段提問

接着，通過一個已知部分準確的問題“當且僅當羅馬在意大利時，da 的意思是嗎？”來確定面對這個問題時 True 和 False 的回答規律，即 True 會說“da”，False 會說“ja”。

三、分析第三階段提問

最後向同一個神提問“當且僅當 A 是隨機神，da 的意思是是嗎？”，通過這個問題的回答以及前面的排除過程，就可以確切地知道三個神分別是誰。 整個推理過程利用了邏輯等價和排除法，通過巧妙的提問設計逐步縮小可能性範圍，最終確定三個神的身份。

怎麼用嵌套問題快速求解？

能不能用之前提到的嵌套的方式來繞開復雜的條件假設呢？答案是可以，這個解法也是目前中文互聯網中最常見的解法，借用知乎文章深入淺出帶你看懂最燒腦邏輯題——布洛斯謎題解題思路來簡單介紹一下。

可以模仿之前的“嵌套問題”，讓三位神站/坐成一排，左到右爲A——B——C

提問策略爲：

1）先向A提問，A地回答爲ja的話接下來對B提問，否則向C提問。

2）第3個提問和第2個都是同一位神。

3）根據提問的得到的回答可以達到8種組合，按照下表可以唯一地確定ABC三位神地身份。

提問則是：
1）假神是在隨機神左邊的答案是da嗎？
2）真神在假神左邊或者隨機在假神右邊的答案是da嗎？
3）da=對嗎？

總結一下

三神謎題的難點在於隨機神的存在讓我們很難構築簡單的問題，迷題的解法也很多，但無論是哪一種，歸根到底相當於把複雜的邏輯層層剝開，一步一步簡化我們的問題設計，最關鍵的是要抓住每個回答所提供的信息。這一點在密碼學中也非常重要，即時僞神給出了錯誤的答案，但是錯誤的答案也同樣提供了信息，可以利用這種信息來分析問題。