天国の門を機械的にくぐる

数学の面白い話してくれ ニュース速報BIP より

門が二つあって、一方は天国に、もう一方は地獄に通じるが、どちらがどちらか分からない。どちらにも門番がいて、一方は真実しか、もう一方は嘘しか言わない。門番はそのことと、自分の守る門がどちらかを知っている。質問を一つだけ、片方の門番だけにすることができる。どうすれば天国への門を選べるか。

有名な問題らしい。今日はこれを解く。

機械的に解く

この手の問題は、あーでもないこーでもないと考えるのが楽しいもの。だけど今日は、機械的に解くにはどうするのかなーと考えた結果、真理値表を使うことにした。まず訊ねる門番と門の組み合わせに対して、どんな解答が欲しいかを考える。

門番＼門	天国行	地獄行
正直者	Yes	No
嘘つき	Yes	No

答えから門を決定するのだから、このように、門番が正直かどうかに関係なく門によって答えが決まる質問をしないといけない。ところで嘘つきは返答を逆転させるので、命題の真偽は

門番＼門	天国行	地獄行
正直者	True	False
嘘つき	False	True

となる。こ、これはXOR…！というわけで、この真理値表を実現する質問を愚直に考えると

あなたは次の二つのうちのどちらかに該当しますか？

1. 正直な天国の門番
2. 嘘つきな地獄の門番

となる。実に微妙な質問だが、これで「はい」とくれば目の前の門をくぐり、「いいえ」とくれば他方の門をくぐればいいことになる。やった！

百門あっても大丈夫

たとえ門や質問が増えても、真理値表さえ書ければこの手の問題は全てこの手で考えることができそう。

スマートな答え

この問題に対するいわゆる正解は

私がこちらは天国に通じるかと聞けばあなたははいと答えますか？

らしい。嘘つきにだけNotがかかる方法、実にスマート。さて、この答えに機械的に辿り着くには、どうするか…。