昨日の
「最も難しい論理パズル」の解答と解説。
色々な考え方と答があるが、おそらく以下が最もエレガントだろう。
まず、尋ねる妖精が正直でも嘘吐きでも、妖精語の「ジャー／ダー」が「はい／いいえ」
のどちらでも、答が知りたい質問Ｘが正しければ「ジャー」、
正しくなければ「ダー」という答が返ってくるような、
質問Ｘを埋め込んだ質問Ｘ’を作成する。
次に、この質問Ｘ’を使って、「ランダム妖精」でない妖精を同定する。
そして、その妖精に対して質問Ｘ’を使い、各妖精の種類を確定する。
「はい／いいえ」で答える二者択一の質問Ｘに対して、 「もしＸと尋ねたら、あなたは『ジャー』と答えますか？」 という質問Ｘ’を考えよう。 すると、この質問に対しては、 尋ねられたのが「正直妖精」でも「嘘吐き妖精」でも、 妖精語の「ダー／ジャー」が「はい／いいえ」のどちらであっても、 埋め込まれた質問Ｘが正しければ「ジャー」、正しくなければ「ダー」と答える。 俄に信じ難いが本当なので、是非ご自分で確認していただきたい。 もし、「ランダム妖精」の意味が、気分次第でその質問に対して正直になったり、嘘吐きになったりする、 ということならば、これで全ての問題が解決したことになる。 三人それぞれに、誰がどの妖精かという質問Ｘを埋め込んで、質問Ｘ’を訊けば良い。
しかし、「ランダム妖精」の定義が、質問を無視して、でたらめに （例えば、コイン投げの結果に応じて）「ジャー」か「ダー」を答える、 ということならば、上のトリックは通用しない。 そこでもう一つアイデアが必要になる。 妖精をＡ，Ｂ，Ｃとして、そのＡに、 「Ｂは『ランダム妖精』ですかと尋ねたら、あなたは『ジャー』と答えますか？」 と尋ねるのだ。 もしＡが「ランダム妖精」でないならば、上のトリックが効いて、 答が「ジャー」ならＢは「ランダム妖精」、「ダー」ならば「ランダム妖精」ではない。 しかし、Ａ自身が「ランダム妖精」ならば、上のトリックは効かないので、 何の情報も得られない……ように思われるが、そうではない。 なぜならば、この場合、Ａが「ランダム妖精」なので、Ｂは（そしてＣも）「ランダム妖精」ではない。 よって、答が「ジャー」ならば、Ｂが「ランダム妖精」であるか、Ａ自身が「ランダム妖精」であり、 いずれにせよＣは「ランダム妖精」ではない。 また、答が「ダー」ならば、Ｂが「ランダム妖精」ではないか、Ａ自身が「ランダム妖精」であり、 いずれにせよＢは「ランダム妖精」ではない。 これによって、「ランダム妖精」ではない妖精が同定できる。
そして、「ランダム妖精」ではない妖精に対して、妖精の種類を確定する質問Ｘ’をすればよい。 例えば、「あなたは『嘘吐き妖精』ですかと尋ねたら、あなたは『ジャー』と答えますか？」と、 「Ｃは『ランダム妖精』ですかと尋ねたら、あなたは『ジャー』」と答えますか？」など。 （もし、質問は各妖精に対し一つずつに限る、という条件を付けると、答はないと（私は）思う。 微妙に異なるバージョンについて、「一人一つ」の場合に解があるかどうか、 あるいは、「全部で二回」の場合に解があるかについて、 いくつか議論と結果があることまでは調べたが、 このバージョンではどうなのか自分で詰め切れなかった。もし分かったら教えて下さい。）
このパズルには微妙に設定の違う（or 設定の曖昧な）バージョンが色々あるのだが、 おそらく起源は論理学者の R.スマリヤンによるもので、 「この本の名は？」(R.Smullyan: "What is the Name of This Book?", (1978))に登場している。 その後、計算機科学者の J.マッカーシーが「ジャー／ダー」が「はい／いいえ」 のどちらか分からないバージョンに拡張したらしい。 それを哲学者で論理学者の G.Boolos が論文 "The Hardest Logic Puzzle Ever"(Harvard Review of Philosophy, No.6, pp.62-65,(1996)) でとりあげて、「最も難しい論理パズル」と呼ばれるようになった。 これが、このパズルを最初に曖昧さのない形で定式化した論文と思われる。 私がこのパズルを知ったのは最近、「最も難しい論理パズルがさらに難しく」 というプレプリントが arXiv に出ていたから ("The hardest logic puzzle ever becomes even tougher")。 この問題に興味を持たれた方は、とりあえず、 Wikipedia 項目 "The Hardest Logic Puzzle Ever" から始めるとよいと思う。
この blog を読んで下さっている方は非常に知的であるようで、 紹介するパズルが高度であればあるほどアクセス数が多い、 という統計が得られている。 今回も最高難易度にチャレンジしてみましたが、どうでしょう？
