2014年11月14日

via io9.com

據說 Raymond Smullyan 曾設計過一個邏輯難題,被 MIT 教授 George Boolos 稱為「有史以來最難的邏輯題」。思方網有中文版
有甲、乙、丙三個精靈,其中一個只說真話,另外一個只說假話,還有一個隨機地決定何時說真話,何時說假話。你可以向這三個精靈發問三條是非題,而你的任務是從他們的答案找出誰說真話,誰說假話,誰是隨機答話。你每次可選擇任何一個精靈問話,問的問題可以取決於上一題的答案。這個難題困難的地方是這些精靈會以「Da」或「Ja」回答,但你並不知道它們的意思,只知道其中一個字代表「對」,另外一個字代表「錯」。你應該問那三條問題呢?
Boolos 在 1996 年發表文章,講解他的答案,該篇文章以 “The Hardest Logic Puzzle Ever” 命名,內容收錄在他 1998 年出版的書 Logic, Logic, and Logic (pp. 406-410) 。他的解答寫得非常好,清楚簡潔(連 “iff” 也解釋),稍為花一點時間便能看懂。

一開始便挑戰這難題,通常只落得個茫無頭緒,然而,這難題其實有提示。 Boolos 在解答前先講三條熱身題,假如三條熱身題都會做,要想到解答便易得多。

熱身題一:
枱面平放三張撲克牌,分別是兩張 Aces 和一張 Jack 。三張牌都背向上,無法看到它們是 A 還是 J 。但你可以指著其中一張牌,問一條是非題 (yes-no question) ,然後透過對方的回答找出一張 A 。假如你指到 A ,對方會答真話;但假如指到 J ,對方就只會隨機答話。你要問甚麼問題來找出 A ?

熱身題二
你面前有一個精露,他可能是只講真話的精靈,可能是只講假話的精靈,你不知道是哪一個,但他講的肯定是英文。假設你想知道杜尚別是不是在吉爾吉斯,但只可問一條是非題。你要問甚麼問題才知道答案?

熱身題三:
你面前有一個只講真話的精靈,但他只會講「Da」或「Ja」。你不知道這兩個字的意思,只知道其中一個代表「對」,另一個代表「錯」。同樣,你只可問一條是非題。你要問甚麼問題才知道杜尚別是不是在吉爾吉斯?

熱身題的解答同樣可在 Boolos 那篇文章找到。

0 comments:

張貼留言

 
Toggle Footer