100匹の十分に論理的なドラゴンの問題で、ドラゴンはそれまで無事に過ごせるか？
ドラゴンの問題とは？
Can You Solve 'The Hardest Logic Puzzle In The World'?などにある、ドラゴンの目のパズルがある。
要約すると以下のような問題文である。
ある島には、目が緑色の100匹のドラゴンがいました。彼らは何世紀もの間人間を見たことがなかったため、訪れたあなたはとても歓迎されています。（ドラゴンは会話できます）
この島には不思議なルールがあります。ドラゴンは、自分の目が緑色だと知ったら、その日の夜中に雀に変身しなければいけないのです。
でもこの島には鏡がなく、目の色について話すこともないため、ドラゴンたちは自分の目の色を知らず、ずっと平和に暮らしてました。
あなたが島を去るとき、ドラゴンは全員見送りのために集まってくれました。あなたはそこで、少なくとも1匹の目が緑色だと告げます。ドラゴンたちが十分論理的だと仮定すると、何が起こるでしょうか？
これの答えは、「100回目の夜中に、100匹のドラゴン全員が雀に変身する」という物です。が、私はこれに対して疑問を持ちました。
とりあえず問題の補足として、
- ドラゴンは毎昼に、同じ場所に集まり、互いに顔を合わせ、目の色を互いに知る
- ドラゴンは互いに全てのドラゴンが十分論理的だと知っている
という前提も付け加えておきます。
この問題には、変身でなく島を去るパターン、ドラゴン以外の生物のパターン（夫婦の不倫など）などがあります。
よくある解説
さて、よくある解説では、ドラゴンが少ない状態から考えています。
答えに納得している人は、ステップ4まで読み飛ばして大丈夫です。
ステップ1：ドラゴンが1匹の場合。
ドラゴン1の知識
- 少なくとも1匹の目は緑色
- （この島にドラゴンは1匹）
ドラゴン1の論理的考察（1日目）
少なくとも1匹の目は緑色なので、ドラゴン1は自分の目が緑色だと知る。
結果
1回目の夜中に全てのドラゴンが雀に変身する。
ステップ2：ドラゴンが2匹の場合。
ドラゴン1の知識
- ドラゴン2の目は緑色
- 少なくとも1匹の目は緑色
- ドラゴン2は「少なくとも1匹の目は緑色」を知っている
- ドラゴン2はドラゴン1（自分）の目の色を知っている
- （この島にドラゴンは2匹）
ドラゴン2も、立場は違えど同じような知識を得ます。
ドラゴン1の論理的考察（1日目）
ドラゴン1は、「少なくとも1匹の目は緑色」「ドラゴン2の目は緑色」だけでは自分の目の色は分かりません。だから、夜中に雀に変身しません。
それだけでなく、十分論理的なドラゴン1は、ドラゴン2の立場で考えます。
もしもドラゴン1（自分）の目の色が緑ではなかった場合、ドラゴン2は「少なくとも1匹の目は緑色」「しかしドラゴン1の目は緑ではない」という2つの知識から、論理的に「自分の目は緑色」を導き、翌昼までには雀の姿になっているはずだと考えます。
ドラゴン2も、立場は違えど同じように考えます。
1回目の夜には何も起きません。
ドラゴン1の論理的考察（2日目）
翌昼、ドラゴン1とドラゴン2は顔を合わせます。どちらも雀に変身していないと気がつきます。
ドラゴン1は、ドラゴン2が雀になっていないことから、ドラゴン1（自分）の目が緑色であることを論理的に導きます（背理法）。ドラゴン2も、立場は違えど同じように考えます。
結果
2回目の夜、ドラゴン1とドラゴン2が（＝全てのドラゴンが）雀に変身します。
このようにドラゴンの情報は対称的なのでドラゴンの動きは全く同じになるはずです。
そして、緑色の目をしていないドラゴンはいてもいなくても他のドラゴンが雀に変身するタイミングとは関係ないことが分かります。そのドラゴンは雀に変身しないし、目の話をしないからです。例えばドラゴン1の目が緑色以外であった場合、1日目にドラゴン2が雀に変身しますが、これはステップ1の「ドラゴンが1匹の場合（ドラゴン2視点）」と同じです。
ステップ3：ドラゴンが3匹の場合。
ドラゴン1の知識
- ドラゴン2とドラゴン3の目は緑色
- 少なくとも1匹の目は緑色
- ドラゴン2もドラゴン3も「少なくとも1匹の目は緑色」を知っている
- ドラゴン2もドラゴン3もドラゴン1（自分）の目の色を知っている
- ドラゴン2はドラゴン3の目が緑だと、ドラゴン3はドラゴン2の目が緑だと知っている
- （この島にドラゴンは3匹）
を知っています。更に言えば、
- ドラゴン2もドラゴン3も、同様に私と同じようなことを知っている
- 例えば、ドラゴン2は「ドラゴン3がドラゴン1の目が緑だと知っている」を知っている
を知っているわけです。ドンドンややこしくなってきました。
ドラゴン1の論理的考察（1日目）
ドラゴン1は、「少なくとも1匹の目は緑色」「ドラゴン2の目は緑色」だけでは自分の目の色は分かりません。だから、夜中に雀に変身しません。
それだけでなく、十分論理的なドラゴン1は、ドラゴン2の立場で考えます。
もしもドラゴン1（自分）の目が緑ではなかった場合、「自分抜きでの問題と同じである。つまり、2匹の緑目のドラゴンがいた場合の「2日後に全てのドラゴンが雀になる」になるはずだ。」と考えます。
ドラゴン1の論理的考察（2日目）
ドラゴン2もドラゴン3も雀に変身していない。でも自分の目の色はまだ分からない。
なぜなら、ドラゴン2が雀に変身していないのはドラゴン3の目が緑だと知っているからだけで十分だからである。
もしも自分の目が緑ではなかったら、ドラゴン2は「ドラゴン1の目は緑じゃないのにドラゴン3が雀ではないということはドラゴン2の目は緑色だと気がついて、翌昼には雀になっているんだろうなあ」と考える。
ドラゴン1の論理的考察（3日目）
ああ、ドラゴン2はドラゴンの姿のままやってきた。つまり…自分の目は緑色である。
結果
3回目の夜、全てのドラゴンが雀に変身します。
さあ、ここまでは私も納得しています。
ステップ4：ドラゴンが4匹の場合。
ドラゴン1の知識
- ドラゴン2とドラゴン3とドラゴン4の目は緑色
- 少なくとも1匹の目は緑色
- ドラゴン2〜4も「少なくとも1匹の目は緑色」を知っている
- ドラゴン2〜4もドラゴン1（自分）の目の色を知っている
- ドラゴン2はドラゴン3やドラゴン4の目が緑だと、ドラゴン3はドラゴン2やドラゴン4の目が緑だと、ドラゴン4はドラゴン2やドラゴン3の目が緑だと知っている
- （この島にドラゴンは4匹）
を知っています。
これまでの議論をパターン化し、4回目の夜に全てのドラゴンが雀に変身すると結論づけます。
そして、100匹の場合は100回目の夜に全てのドラゴンが雀に変身すると結論づけ、それを解答とします。
筆者の疑問
ところで、
- 全てのドラゴンが、「少なくとも1匹の目は緑色」を知っている
という知識は、旅人から聞かなければ分からないのでしょうか？
筆者の考え
ドラゴンが4匹の場合を考えてみましょう。
ドラゴン1は、ドラゴン2がドラゴン3とドラゴン4の目を見ていることを知っています。
ドラゴン2は、ドラゴン1の目の色・ドラゴン2の目の色に関わらず、ドラゴン3はドラゴン4の目が緑色だと知っていることを知っています。
ドラゴン1は、上記の「ドラゴン2は、ドラゴン1の目の色・ドラゴン2の目の色に関わらず、ドラゴン3はドラゴン4の目を見ていることを知っています。」を知っています。
同様に、
ドラゴン1は、上記の「ドラゴン2は、ドラゴン1の目の色・ドラゴン2の目の色に関わらず、ドラゴン4はドラゴン3の目を見ていることを知っています。」を知っています。
つまり、
ドラゴン1は、「ドラゴン2が、「ドラゴン3が少なくとも1匹の目は緑色であると知っている」を知っている」を知っています。
同様に、
ドラゴン1は、「ドラゴン2が、「ドラゴン4が少なくとも1匹の目は緑色であると知っている」を知っている」も知っています。
更に同様に、
ドラゴン1は、「ドラゴン3が、「ドラゴン2が少なくとも1匹の目は緑色であると知っている」を知っている」も知っています。
ドラゴン1は、「ドラゴン3が、「ドラゴン4が少なくとも1匹の目は緑色であると知っている」を知っている」も知っています。
ドラゴン1は、「ドラゴン4が、「ドラゴン2が少なくとも1匹の目は緑色であると知っている」を知っている」も知っています。
ドラゴン1は、「ドラゴン4が、「ドラゴン3が少なくとも1匹の目は緑色であると知っている」を知っている」も知っています。
ということは、
ドラゴン1は、「この島の全てのドラゴンが、「この島の全てのドラゴンが、少なくとも1匹の目は緑色であると知っている」を知っている」を知れます。
そして、ドラゴン2〜4も「この島の全てのドラゴンが、「この島の全てのドラゴンが、少なくとも1匹の目は緑色であると知っている」を知っている」を知れます。
ドラゴンが十分に論理的であれば、旅人が「少なくとも1匹は緑色の目をしている」といわなくても、ドラゴンが4匹なら全てのドラゴンが「少なくとも1匹は緑色の目をしている」という知識を共有できている事を知っているはずです。
ならば、旅人の発言を待たずして雀に変身するのではないか？
100匹のドラゴンがいた場合、毎日昼に各ドラゴンは、「この島の全てのドラゴンが、「この島の全てのドラゴンが、少なくとも97匹の目は緑色であると知っている」を知っている」を知れます。そしてやはり4回目の夜に、全ドラゴンが雀に変身するのではないか..？
と一瞬思いましたが、論理の足りなさに気がつきました。
2匹のドラゴンが雀に変わるためには「ドラゴン1が、「ドラゴン2が、「1匹の目は緑色である」と知っている」と知っている」を条件としています。
同様に
3匹のドラゴンが雀に変わるためには「ドラゴン1が、「ドラゴン2が、「ドラゴン3が、「1匹の目は緑色である」と知っている」と知っている」と知っている」を条件としています。
4匹のドラゴンが雀に変わるためには「ドラゴン1が、「ドラゴン2が、「ドラゴン3が、「ドラゴン4が、「1匹の目は緑色である」と知っている」と知っている」と知っている」と知っている」を条件としています。
一方で旅人の発言前には「ドラゴン1が、「ドラゴン2が、「ドラゴン3が、「1匹の目は緑色である」と知っている」と知っている」と知っている」までは論理的に到達できても、「ドラゴン1が、「ドラゴン2が、「ドラゴン3が、「ドラゴン4が「1匹の目は緑色である」と知っている」と知っている」と知っている」と知っている」かは分かりません。
なぜなら、ドラゴン1は自分の目が緑色ではないかも知れないと思いながら推論で始め、ドラゴン2もドラゴン3も自分の目が緑色ではないかも知れないと思いながら推論するからです。
他の記事・解説動画での解答の扱い
この問題を扱っている記事を探してみました。google検索で10件ほど開いただけなので同じような記事ばかりでした。同じ発想をした人がいるのだろうか。
記事1: 論理クイズ「幼女とドラゴンの島」で未来を予知できるか - 明日は未来だ！
ドラゴンが2匹までの場合を具体的に述べた後、特に説明も無くn匹に一般化している。一般化の論理が雑。
記事2: 論理クイズ １００匹のドラゴン | Handyman志木店
ドラゴンが3匹の場合までのことを述べている。「自分の目の色が緑でなければn-1日目に変身する」という数学的帰納法を使っている。ただし厳密には、少なくともn-1日目までに変身するという論理でしかない気がする。それより早く気がつけない証明がない。
記事3: 緑色の目をしたドラゴンの問題について考察 - Qiita
記事2とほぼ同様。上記ドラゴンが4匹の場合までのことを述べている。「自分の目の色が緑でなければn-1日目に変身する」という数学的帰納法を使っている。ただし厳密には、少なくともn-1日目までに変身するという論理でしかない気がする。それより早く気がつけない証明がない。
また、「もし何かがドラゴン達に起こったとすれば、あなたがドラゴン達に与えた情報の本質は一体何だったのでしょうか？」という問いに対し、「少なくとも99匹のドラゴンが緑の目をしていることを、99日後に彼らの共有知識にした。」と述べている。
記事4: 理科とか苦手で 「緑色の目をしたドラゴン」 を解説してみた （中編）
記事2とほぼ同様。ただし後編の記事で、「いずれにしろ、ドラゴンBは少なくとも９８頭のドラゴンが緑の目をしていることを知っている。ここまでは、ドラゴンＡは確証が持てるのです。」と書かれています。
記事5: ドラゴンの目の論理パズルを知ったのだけど納得できない(納得できた)
既存の解説が理解できていない人が理解していく様子。ドラゴンが5匹の場合までのことをとても具体的に述べている。それ以前に気がつけるかどうかには言及無し
記事6以降:
答えが分かれば超簡単！ハーバード大学の出す「世界で最も難しい論理パズル」皆さん解けますか？ : ユルクヤル、外国人から見た世界
難問の論理・数理パズルに挑戦しよう【赤目の村】 | 興味の窓
「もし何かがドラゴン達に起こったとすれば、あなたがドラゴン達に与えた情報の本質は一体何だったのでしょうか？」という問いに対し、「少なくとも99匹のドラゴンが緑の目をしていることを、99日後に彼らの共有知識にした。」と述べている。
結果としてはそうだけど「情報」の本質は違うと思っています。
私の思う答えは、「ドラゴン1が、「ドラゴン2が...「ドラゴン100が、「1匹の目は緑色である」と知っている」...と知っている」と知っている」という情報、だと思います。
与えた情報としては「と知っている」100回分の繰り返しだけでなく無限回の繰り返しを可能とするような情報ですが、少なくとも100回分の"メタ"知識を与えれば雀に変身するので。
