「夫子憮然曰、鳥獣不可與同羣。吾非斯人之徒與、而誰與。
「論語」微子、第十八、六

2012/06/24

最も難しい論理パズル(解答)

昨日の 「最も難しい論理パズル」の解答と解説。
色々な考え方と答があるが、おそらく以下が最もエレガントだろう。 まず、尋ねる妖精が正直でも嘘吐きでも、妖精語の「ジャー/ダー」が「はい/いいえ」 のどちらでも、答が知りたい質問Xが正しければ「ジャー」、 正しくなければ「ダー」という答が返ってくるような、 質問Xを埋め込んだ質問X’を作成する。 次に、この質問X’を使って、「ランダム妖精」でない妖精を同定する。 そして、その妖精に対して質問X’を使い、各妖精の種類を確定する。

「はい/いいえ」で答える二者択一の質問Xに対して、 「もしXと尋ねたら、あなたは『ジャー』と答えますか?」 という質問X’を考えよう。 すると、この質問に対しては、 尋ねられたのが「正直妖精」でも「嘘吐き妖精」でも、 妖精語の「ダー/ジャー」が「はい/いいえ」のどちらであっても、 埋め込まれた質問Xが正しければ「ジャー」、正しくなければ「ダー」と答える。 俄に信じ難いが本当なので、是非ご自分で確認していただきたい。 もし、「ランダム妖精」の意味が、気分次第でその質問に対して正直になったり、嘘吐きになったりする、 ということならば、これで全ての問題が解決したことになる。 三人それぞれに、誰がどの妖精かという質問Xを埋め込んで、質問X’を訊けば良い。

しかし、「ランダム妖精」の定義が、質問を無視して、でたらめに (例えば、コイン投げの結果に応じて)「ジャー」か「ダー」を答える、 ということならば、上のトリックは通用しない。 そこでもう一つアイデアが必要になる。 妖精をA,B,Cとして、そのAに、 「Bは『ランダム妖精』ですかと尋ねたら、あなたは『ジャー』と答えますか?」 と尋ねるのだ。 もしAが「ランダム妖精」でないならば、上のトリックが効いて、 答が「ジャー」ならBは「ランダム妖精」、「ダー」ならば「ランダム妖精」ではない。 しかし、A自身が「ランダム妖精」ならば、上のトリックは効かないので、 何の情報も得られない……ように思われるが、そうではない。 なぜならば、この場合、Aが「ランダム妖精」なので、Bは(そしてCも)「ランダム妖精」ではない。 よって、答が「ジャー」ならば、Bが「ランダム妖精」であるか、A自身が「ランダム妖精」であり、 いずれにせよCは「ランダム妖精」ではない。 また、答が「ダー」ならば、Bが「ランダム妖精」ではないか、A自身が「ランダム妖精」であり、 いずれにせよBは「ランダム妖精」ではない。 これによって、「ランダム妖精」ではない妖精が同定できる。

そして、「ランダム妖精」ではない妖精に対して、妖精の種類を確定する質問X’をすればよい。 例えば、「あなたは『嘘吐き妖精』ですかと尋ねたら、あなたは『ジャー』と答えますか?」と、 「Cは『ランダム妖精』ですかと尋ねたら、あなたは『ジャー』」と答えますか?」など。 (もし、質問は各妖精に対し一つずつに限る、という条件を付けると、答はないと(私は)思う。 微妙に異なるバージョンについて、「一人一つ」の場合に解があるかどうか、 あるいは、「全部で二回」の場合に解があるかについて、 いくつか議論と結果があることまでは調べたが、 このバージョンではどうなのか自分で詰め切れなかった。もし分かったら教えて下さい。)

このパズルには微妙に設定の違う(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 を読んで下さっている方は非常に知的であるようで、 紹介するパズルが高度であればあるほどアクセス数が多い、 という統計が得られている。 今回も最高難易度にチャレンジしてみましたが、どうでしょう?