「史上最も難しい論理パズル」（The Hardest Logic Puzzle Ever）と名づけられたパズル*1がおもしろかったので、紹介します。
３人の神様Ａ、Ｂ、Ｃがいる。彼らにはシン、ギ、ランという名前があるが、Ａ、Ｂ、Ｃの誰がどの名前を持つかをあなたは知らない。（ただし神様同士はお互いの名前を知っている。）シンは常に正しいことを話し、ギは常に嘘を話すが、ランが正しいことを話すか嘘を話すかは完全にランダムである。あなたに課せられた課題は、ＹＥＳ／ＮＯクエスチョン（ＹＥＳかＮＯで答えられる質問）を３回することによって、Ａ、Ｂ、Ｃの正体を特定することである。ただし各質問は、ただ１人の神様に向けて行うものとする。神様は人間の言葉を理解するが、回答は彼ら独自の言語で行われる。その言語では「ＹＥＳ」と「ＮＯ」に相当する言葉は「ダ」と「ジャ」だが、どっちがどっちを意味するのかをあなたは知らない。
注意３点：
［１］ある神様が複数回の質問を受けることがありえる。（したがって、その場合には質問を全くされない神様がいる。）
［２］２回目の質問内容、またそれを誰に回答してもらうかは、１回目の質問に対する回答に依存してもよい。（そして当然、３回目の質問に対しても同様のことがいえる。）
［３］ランが本当のことを話すかどうかは、彼の頭の中で秘密裏に行われるコイントスによって次のように決定されると考えてよい。：コインの表が出れば本当のことを話し、裏が出れば嘘を話す。
最後の邪悪なヒネリには笑ってしまいますね。「ダ」と「ジャ」がどっちを意味するのか分からないんですって。うへぇ、これは難しい。
でももし、おもしろそう！と感じたら、根気よく考えてみてください。楽しい時間が過ごせます。こういう問題を考えるコツはいろいろありますが、私が有効だと思うのは以下のようなものです。
- 大きめの紙を用意して、そこで“実験”を行う。例えば、神様に問う質問で意味のありそうなものを思いつくままに書きだしてみて、それに対する神様の返答を、場合分けを慎重にしつつ、観察する。
- パズルの簡単なバージョンを自分でいろいろつくってそれを解いてみる。例えば、
- 神様が人間の言葉で回答してくれるんだったら？
- 質問が３回ではなく１０回まで許されていたら？
- Ａの名前がランだとあらかじめ分かっていたとしたら？
- その他いろいろ
- 興味をもってくれそうな友人に説明して、アイデアを交換する。
- 自分にはこの問題が解けるのだ！と心の底から信じて数日間、数週間という単位で没頭する。
ここに解答は載せません。健闘を祈ります。
補足１：
個人的には、ランの挙動［３］は、次の［３’］を採用した方がより難しくなって楽しいと思う。（［３］にするか［３’］にするかで違いが生まれることが信じられない？えぇ、ネタバレになるから説明はしませんが、確かにこの２つには本質的な違いがあるんです。）
- ［３’］ランが「ダ」と答えるか「ジャ」と答えるかは、彼の頭の中で秘密裏に行われるコイントスによって次のように決定されると考えてよい。：コインの表が出れば「ダ」と答え、裏が出れば「ジャ」と答える。（つまりランは質問の内容を全く聞いていない。）
補足２：
ＹＥＳ／ＮＯクエスチョンの定義については、ちょっとだけ微妙なところがある。一見、ＹＥＳ／ＮＯクエスチョンにみえる質問が、ある状況下ではYESともNOとも答えられない質問になってしまうことがありうる。当然、そのような可能性のある質問は禁止されていると考えるべきである。
補足３：
ＹＥＳ／ＮＯクエスチョンの定義の拡張だとか、問題にさらなるヒネリを加えて難しくするだとかの議論がいくつかなされている。詳しくは英語版ウィキペディア（注意！リンク先に解答あり）を参照のこと。
追記：こういう論理パズルに興味がある人には、『スマリヤンの究極の論理パズル―数の不思議からゲーデルの定理へ』をおすすめします。
*1:論理学者George Boolosによって発表された。彼は論文の中で、これの原型となったパズルは論理学者レイモンド・スマリヤンによる発案であり、また、“神様の言葉の意味をあなたは知らない”という、問題を難しくするための一工夫は計算機科学者ジョン・マッカーシーのアイデアだと述べている。
