0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

「史上最も難しい論理パズル」(The Hardest Logic Puzzle Ever)が大したことないと思える記事

Posted at

概要

史上最も難しい論理パズル」(The Hardest Logic Puzzle Ever)と呼ばれるパズルがあります。
以下のものです。(参考:https://b.log456.com/entry/20120825/p1)

3人の神様A、B、Cがいる。彼らにはシン、ギ、ランという名前があるが、A、B、Cの誰がどの名前を持つかをあなたは知らない。(ただし神様同士はお互いの名前を知っている。)シンは常に正しいことを話し、ギは常に嘘を話すが、ランが正しいことを話すか嘘を話すかは完全にランダムである。あなたに課せられた課題は、YES/NOクエスチョン(YESかNOで答えられる質問)を3回することによって、A、B、Cの正体を特定することである。ただし各質問は、ただ1人の神様に向けて行うものとする。神様は人間の言葉を理解するが、回答は彼ら独自の言語で行われる。その言語では「YES」と「NO」に相当する言葉は「ダ」と「ジャ」だが、どっちがどっちを意味するのかをあなたは知らない。

注意3点:

[1]ある神様が複数回の質問を受けることがありえる。(したがって、その場合には質問を全くされない神様がいる。)

[2]2回目の質問内容、またそれを誰に回答してもらうかは、1回目の質問に対する回答に依存してもよい。(そして当然、3回目の質問に対しても同様のことがいえる。)

[3]ランが本当のことを話すかどうかは、彼の頭の中で秘密裏に行われるコイントスによって次のように決定されると考えてよい。:コインの表が出れば本当のことを話し、裏が出れば嘘を話す。

確かに問題を読むと「できるかアホ!!」と言いたくなるくらい複雑ですが、一歩ずつ進んでいくと意外と大したことないことがわかります。
自信のある方は解いてみるといいと思います。多分解法はたくさんあります。
また注意点の3は特に大事で、ランはダとジャをランダムでいうわけではなく、真実か嘘をいうのがポイントです。

解き方

こういった嘘つき系のパズルではよく出る技ですが、以下のように聞くと嘘つきでも正直者でも正しく答えてくれます。

「「X=Yか?」の回答はYESか?」 or 「「X=Yか?」の回答はNOか?」

たとえば前者の聞き方をした場合、
X=Yが正しい時は正直者ならYES、嘘つきでもYESと答えます。
そしてX=Yが正しくない時は正直者ならNO、嘘つきでもNOと答えます。
後者の聞き方であれば
X=Yが正しい時は正直者ならNO、嘘つきでもNOと答えます。
そしてX=Yが正しくない時は正直者ならYES、嘘つきでもYESと答えます。
ここで、前者の質問と後者の質問で回答がまるまるひっくり返っていることを考えると、

「「X=Yか?」の回答はジャか?」

と聞けば常に真実を話してくれます。

たとえば「横浜は東京か?の回答はジャか?」のように聞くと、シンもギもランも「ダ」と答えます。
よってAに

「「Aはシンか?」の回答はジャか?」

のように聞くことでAがシンかどうかがわかります。
念の為全てのパターンで確認します。

Aの正体 ジャの意味 回答
シン YES ジャ
シン NO ジャ
YES
NO
ラン(シン) YES
ラン(シン) NO
ラン(ギ) YES
ラン(ギ) NO

というように、Aがシンの場合のみジャと答えてくれます。
もはやこの問題は以下のように言い換えられます。

A,B,Cの三人の神がおり、全員どんな質問にも正しくYESかNOで回答します。
彼らにはシン、ギ、ランという名前がありますがどの神がどの名前なのかがわかりません。
これを3回の質問で特定してください

ここまできたら本当に大したことないです。
解答載せるまでもないかもしれませんが、一応下記の通りです。

まず、Aに「シンですか?」と聞く
YESの場合、Bに「ギですか?」と聞き、消去法で特定完了
NOの場合、Aに「ギですか?」と聞きAを特定
次にBに「シンですか?」と聞き特定完了

まあ3の階乗が6で2の3乗が8なので、多分どんな聞き方しても特定できるとは思います。

まとめ

この問題について調べてみると、もっと複雑な答えが出てきます。(wiki参照)
ただこの解答がいちばんシンプルでわかりやすいんじゃないかと思い紹介しました。

この問題は世界一難しいとされていますが、ランの仕様を「ダとジャをランダムで答える」と言ったものにした方がより難しいと思います。
この場合はより複雑な解法が存在しますが、ランでないものを一人用意できれば今回と同じようにやりたい放題になるので、その一捻りだけ頑張れば終わりです。

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?