世界で一番難しい論理パズル

https://www.newscientist.com/article/dn22357-three-gods-the-hardest-logic-puzzle-ever/

「世界で一番◯◯なもの」を決めることほど、神経質な人間にとって困難なことはない。

しかし、パズルの世界にはこれが存在する。

なぜならば、そのパズルの名前自体が「The hardest logic puzzle ever（史上最も難しい論理パズル、世界で一番難しい論理パズル）」であるからだ。

出題

問。A、B、Cと呼ばれる3柱の神がいて、このうちのいずれかがそれぞれ”真”、”偽”、”無作為”の神である。真は常に正直なことを話し、偽は常に嘘をつくが、無作為が正直に話すか嘘をつくかは、その都度全くランダムに決まる。あなたはA、B、Cに「はい」か「いいえ」で答えられる質問を3回行い、それぞれの神の正体を暴かねばならない。ただし、それぞれの質問は1柱の神に対してしか行うことができない（筆者注：AとBに同じ内容の質問をした場合、これは2回の質問をしたとみなす）。神々は日本語を理解できるが、その質問に対する返答は神々の言葉「Da」か「Ja」で行われる。これらの言葉は日本語の「はい／いいえ」に相当する。しかし、「Da」と「Ja」のどちらが「はい」または「いいえ」を意味するかはわからない。

さらに、このパズルには補足がある。

1. 1柱の神に対して2つ以上の質問をすることができる。（したがって、1回も質問されない神がいても良い）
2. 2つ目の質問内容をどうするか、どの神に質問するかは1つ目の質問の答えを参考に決めて良い。（そしてもちろん、3つ目の質問も同様である）
3. ”無作為”が正直に話すか嘘をつくかは、彼が頭の中でこっそりコイン・トスをして決めるとして考えてよい。表が出たときは正直に、裏が出たときは嘘を答えるという感じである。
4. ”無作為”はいかなる質問に対しても”Da”または”Ja”で答える。

また、当記事ではこの問題をより考えやすくするため、もう1つの条件を設定する。

”無作為”は自身の答え方によらず、常に自身が”無作為”であるとして答える。（例えば、その時”無作為”が正直に答えようとしているからといって、彼が”真”のフリをして答えることはない）

少々難しい問題ではあるが、パズルに自信のある人、時間のある人は是非挑戦してみてほしい。

解説

このパズルは「世界で一番難しい」と謳っておきながら、論理パズルに慣れた人にとっては比較的簡単に解答が出せる。

ここで、もう少し簡単な類題を考えてみよう。

目の前に1柱の神がいる。この神は”真”または”偽”のいずれかである。”真”は常に正直に話し、”偽”は常に嘘をつく神である。あなたはこの神に「はい」か「いいえ」で答えられる質問を1回だけ行い、この神の正体を暴かねばならない。さて、どのような質問をしたら良いか？

この問題の答えは、「『あなたは”真”ですか』と私が訊いたとき、あなたは『はい』と答えますか？」である。

この質問を前・後半に分けて考えてみると、

となり、前半に対しては”真”・”偽”ともに「はい」と答えるが、後半が加わることで最終的な答えが分かれる。

これは1つの質問の中に実質2つの質問を入れることで、”偽”に2回嘘をつかせて、結局正直なことを言わせるという手法である。

つまり、裏の裏は表、という理論だ。

よって、「はい」が返ってきたら”真”、「いいえ」が返ってきたら”偽”となる。

これと同じ手法を今回の問題にも使ってみよう。

例えば、Aに「『あなたは”真”ですか』と私が訊いたとき、あなたは『Da』と答えますか？」と訊いてみる。

この質問の結果を、Aが”真”、”偽”、”無作為（正直なとき）”、”無作為（嘘つきなとき）”の場合にわけて考えてみる。ただし、このとき「Da」が「はい」、「いいえ」のいずれの意味を持つかによってさらに場合分けが必要である。

1. 「Da」＝「はい」のとき
   

   Aの正体	あなたは”真”ですか？	『Da』と答えますか？
   真	Da	Da
   偽	Da	Ja
   無作為（正直）	Ja	Ja
   無作為（嘘）	Da	Ja

2. 「Da」＝「いいえ」のとき
   

   Aの正体	あなたは”真”ですか？	『Da』と答えますか？
   真	Ja	Da
   偽	Ja	Ja
   無作為（正直）	Da	Ja
   無作為（嘘）	Ja	Ja

以上より、「Da」がいずれの意味を持つかには関係なく、Aが”真”である場合のみ「Da」という答えが返ってくることがわかる。

これをさらに拡張すると、実はAに対する「『あなたは”X”ですか』と私が訊いたとき、あなたは『Y』と答えますか？」という質問の答えは、AがX本人（神）であるときのみ、「Y」になるという法則がある。

（例えば「『あなたは”無作為”ですか』と私が訊いたとき、あなたは『Ja』と答えますか？」という質問に対しては、”無作為”のみが「Ja」と返答し、それ以外は「Da」）

したがって、例えば次のような解答が考えられよう。

1. Aに「『あなたは”真”ですか』と私が訊いたとき、あなたは『Da』と答えますか？」と質問する
   1. 「Da」ならAは”真”。（→2.i.へ）
   2. 「Ja」ならばAは”偽”か”無作為”。（→2.ii.へ）
2. Bに
   1. 「『あなたは”偽”ですか』と私が訊いたとき、あなたは『Da』と答えますか？」と質問する
      1. 「Da」ならばBは”偽”。消去法でCは”無作為”。（終了）
      2. 「Ja」ならばCが”偽”、Bは”無作為”。（終了）
   2. 「『あなたは”真”ですか』と私が訊いたとき、あなたは『Da』と答えますか？」と質問する
      1. 「Da」ならばBは”真”。（→3.へ）
      2. 「Ja」ならば消去法でCが”真”。（→3.へ）
3. もう一度Aに「『あなたは”偽”ですか』と私が訊いたとき、あなたは『Da』と答えますか？」と質問する
   1. 「Da」ならばAは”偽”。残り1柱は”無作為”。
   2. 「Ja」ならばAは”無作為”。残り1柱は”偽”。

まとめ、そしてさらに難しく

この手の論理パズルは大体手法が決まっているため、さほど難しくはない。

ようは2重の質問をぶつけることによって、全員を正直者にしてしまえば良いのだ。

しかし、今回の問題の条件を少し変更すると、もう少し難易度を高めることができる。

それは……

”無作為”はコイン・トスで「正直」or「嘘つき」を決めるのではなく、ただ返答で「Da」or「Ja」のいずれを言うかを決める。

という条件である。

すなわち”無作為”は表を用いて説明したような思考手順によって返答を決めるのではなく、いかなる質問に対しても（その意図を読み取らず）「Da」または「Ja」とそれぞれ1/2の確率で答えるとする。

さて、この場合の解決法は？

解答はこちらのページ（参考文献2.）で確認してほしい。

参考文献

1. Brian Rabern, Landon Rabern "A simple solution to the hardest logic puzzle ever", pp. 105-112 (https://dl.dropboxusercontent.com/u/4458028/sshlpe.pdf)
2. The Adventures of Dr. Hara --最も難しい論理パズル（解答）
3. Three gods: The hardest logic puzzle ever | New Scientist