「世界で一番◯◯なもの」を決めることほど、神経質な人間にとって困難なことはありません。
しかし、パズルの世界にはこれが存在します。
なぜならば、そのパズルの名前自体が「The hardest logic puzzle ever」であるからです。
この記事では「世界で一番難しい論理パズル」を例に、正直・嘘つき問題と呼ばれる論理問題の解き方と、その応用例について解説します。
とくに二重質問という技術に焦点をあて、それがなぜうまくいくのかについて、ひとつひとつ場合分けしながら見ていきます。
出題
問。
A、B、Cと呼ばれる３柱の神がいて、このうちのいずれかがそれぞれ”真”、”偽”、”無作為”の神である。
真は常に正直なことを話し、偽は常に嘘をつくが、無作為が正直に話すか嘘をつくかは、その都度全くランダムに決まる。
あなたはA、B、Cに「はい」か「いいえ」で答えられる質問を３回まで行い、それぞれの神の正体を暴かねばならない。
ただし、それぞれの質問は１柱の神に対してしか行うことができない（筆者注：AとBに同じ内容の質問をした場合、これは２回の質問をしたとみなす）。
神々は日本語を理解できるが、その質問に対する返答は神々の言葉「Da」か「Ja」で行われる。
これらの言葉は日本語の「はい／いいえ」に相当する。
しかし、「Da」と「Ja」のどちらが「はい」または「いいえ」を意味するかはわからない。
さらに、このパズルには補足があります。
- １柱の神に対して２つ以上の質問をすることができる。（したがって、1回も質問されない神がいても良い）
- ２つ目の質問内容をどうするか、どの神に質問するかは１つ目の質問の答えを参考に決めて良い。（そしてもちろん、3つ目の質問も同様である）
- ”無作為”が正直に話すか嘘をつくかは、彼が頭の中でこっそりコイン・トスをして決めるとして考えてよい。表が出たときは正直に、裏が出たときは嘘を答えるという感じである。
- ”無作為”はいかなる質問に対しても”Da”または”Ja”で答える。
また、当記事ではこの問題をより考えやすくするため、もう１つの条件を設定しました。
”無作為”は自身の答え方によらず、常に自身が”無作為”であるとして答える。
（例えば、その時”無作為”が正直に答えようとしているとする。このとき、「あなたは"真"ですか？」の質問に対しては、「いいえ」に相当する言葉で回答する。）
解答時間
少々難しい問題ではありますが、パズルに自信のある人、時間のある人は、ぜひ挑戦してみてください。
解説
このパズルは「世界で一番難しい」と謳っておきながら、実は論理パズルに慣れた人にとっては、比較的簡単に解答が出せる問題です。
正直・嘘つき問題の基本形
ここで、もう少し簡単な類題を考えてみましょう。
目の前に１柱の神がいる。
この神は”真”または”偽”のいずれかである。
”真”は常に正直に話し、”偽”は常に嘘をつく神である。
あなたはこの神に「はい」か「いいえ」で答えられる質問を１回だけ行い、この神の正体を暴かねばならない。
さて、どのような質問をしたら良いか？
この問題の答えは、
「『あなたは”真”ですか』と私がたずねたとき、あなたは『はい』と答えますか？」
です。
この質問を前・後半に分けて、それぞれに対する返答を考えてみると、
| 正体 | あなたは”真”ですか？ | 『はい』と答えますか？ |
|---|---|---|
| 真 | はい | はい |
| 偽 | はい | いいえ |
となり、前半に対しては”真”・”偽”ともに「はい」と答えるものの、後半が加わることで最終的な答えが分かれます。
これは１回の質問の中に実質２つの質問を入れることで、”偽”に２回嘘をつかせて、結局正直なことを言わせるという二重質問の手法です。
つまり、裏の裏は表、という理論です。
よって、「はい」が返ってきたら”真”、「いいえ」が返ってきたら”偽”が正体になります。
世界で一番難しい論理パズルへの応用
これと同じ手法を今回の問題にも使ってみましょう。
例えば、Aに「『あなたは”真”ですか』と私がたずねたとき、あなたは『Da』と答えますか？」と質問します。
この質問の結果を、Aの正体が”真”、”偽”、”無作為（正直に返答）”、”無作為（嘘で返答）”の場合にわけて考えてみます。
ただし、このとき「Da」が「はい」、「いいえ」のいずれの意味を持つかによってさらに場合分けが必要です。
「Da」＝「はい」のとき
| Aの正体 | あなたは”真”ですか？ | 『Da』と答えますか？ |
|---|---|---|
| 真 | Da | Da |
| 偽 | Da | Ja |
| 無作為（正直） | Ja | Ja |
| 無作為（嘘） | Da | Ja |
「Da」＝「いいえ」のとき
| Aの正体 | あなたは”真”ですか？ | 『Da』と答えますか？ |
|---|---|---|
| 真 | Ja | Da |
| 偽 | Ja | Ja |
| 無作為（正直） | Da | Ja |
| 無作為（嘘） | Ja | Ja |
まとめと一般化
以上より、「Da」がいずれの意味を持つかには関係なく、Aが”真”である場合のみ「Da」という答えが返ってくることがわかります。
これをさらに拡張すると、実はAに対する
「『あなたは”X”ですか』と私が訊いたとき、あなたは『Y』と答えますか？」
という質問の答えは、AがX本人（神）であるときのみ、「Y」になるという法則がある。
（例えば「『あなたは”無作為”ですか』と私が訊いたとき、あなたは『Ja』と答えますか？」という質問に対しては、”無作為”のみが「Ja」と返答し、それ以外は「Da」）
したがって、例えば次のような解答が考えられます。
- Aに「『あなたは”真”ですか』と私が訊いたとき、あなたは『Da』と答えますか？」と質問する
- 「Da」ならばAは”真”。（→2.1.へ）
- 「Ja」ならばAは”偽”か”無作為”。（→2.2.へ）
- Bに
- 「『あなたは”偽”ですか』と私が訊いたとき、あなたは『Da』と答えますか？」と質問する
- 「Da」ならばBは”偽”。消去法でCは”無作為”。（終了）
- 「Ja」ならばCが”偽”、Bは”無作為”。（終了）
- 「『あなたは”真”ですか』と私が訊いたとき、あなたは『Da』と答えますか？」と質問する
- 「Da」ならばBは”真”。（→3.へ）
- 「Ja」ならば消去法でCが”真”。（→3.へ）
- 「『あなたは”偽”ですか』と私が訊いたとき、あなたは『Da』と答えますか？」と質問する
- もう一度Aに「『あなたは”偽”ですか』と私が訊いたとき、あなたは『Da』と答えますか？」と質問する
- 「Da」ならばAは”偽”。残り1柱は”無作為”。
- 「Ja」ならばAは”無作為”。残り1柱は”偽”。
まとめ、そしてさらに難しく
このように、この手の論理パズルは大体手法が決まっているため、さほど難しくはありません。
ようは2重の質問をぶつけることによって、全員を正直者にしてしまえば解決です。
しかし、今回の問題の条件を少し変更すると、もう少し難易度を高めることができます。
その方法とは……
”無作為”はコイン・トスで「正直に返答」or「嘘で返答」を決めるのではなく、ただ「Da」or「Ja」のいずれを言うかを決める。
という条件に変更することです。
すなわち”無作為”は表を用いて説明したような思考手順によって返答を決めるのではなく、いかなる質問に対しても（その意図を読み取らず）「Da」または「Ja」とそれぞれ1/2の確率で答えるとします。
さて、この場合の解決法は？
解答はこちらのページ（参考文献2.）で確認してください。
コメント