超難問論理クイズ「幼女と7枚のカード」が難しいけど面白すぎる

ものすごく簡単そうなのに、最高レベルに難しい論理クイズ。

あまり例を見ない「あるポイント」でも有名になった「幼女と7枚のカード」に挑戦してみましょう。

元となった問題は、2000年のMOSCOW MATHEMATICAL OLYMPIADS（モスクワ数学オリンピック）で出題されたもの。

まずは予備知識なしでお読みください。

問題

1〜7の数字が書かれた7枚のカードがある。
これをよくシャッフルして幼女ABCの3人に以下のように配る。

幼女Aにはカード3枚
幼女Bにはカード3枚
幼女Cにはカード1枚

まず、幼女Aは自身のカードを見て、何らかの「真実（であると認識していること）」を宣言する。

続いて、幼女Bも自身のカードを見て、何らかの「真実（であると認識していること）」を宣言する。

これらの宣言は全幼女に聞こえる。

いま、これらの行動が行われたところ、幼女Aは幼女Bのカードが何なのかを完全に把握した（すなわち「Cのカードが何なのか」も分かった）。
同様に、幼女Bも幼女Aのカードが何なのかを完全に把握した（すなわち「Cのカードが何なのか」も分かった）。

だが、全く同じ情報を聞いていたはずの幼女Cは誰が何のカードを持っているのかが分からないままだった。

いったい、AとBはどのようなことを言ったのだろうか？

なお、「AとBが事前に打ち合わせること」「AとBの間でのみ通じる暗号を使う」「Cにバレないように上記以外の何らかのコミュニケーションを取ること」は禁じられている。

最後に、すべての幼女はきわめて論理的である。

さあ、解いてみよう！

内容を理解するのは簡単ですね。

解くのは不可能っぽいですね。

何なのだこれは……。

個人的に本問は最高難易度の論理クイズだと認識しており、
「2人の幼女とチェス盤の部屋」
「幼女と3人の神」
に匹敵する難しさです。

覚悟して挑みましょう。

以下では「問題のポイント」「ヒント」「正解」「解説」と続きます。

ノーヒントで解きたい方は「問題のポイント」のみご覧ください。

問題のポイント

不可解な宣言

まず、幼女Aは自身のカードを見て、何らかの「真実（であると認識していること）」を宣言する。

続いて、幼女Bも自身のカードを見て、何らかの「真実（であると認識していること）」を宣言する。

これにより幼女AもBも全員のカードの内訳を把握した。

だが、全く同じ情報を聞いていたはずの幼女Cは誰が何のカードを持っているのかが分からないままだった。

本問を特徴づける最大の要素。

幼女の宣言は、全員に聞こえる。
全員が、同じ情報を聞いている。

なのに幼女AとBだけ「誰が何のカードを持っているか」を完璧に理解し、幼女Cは「自分のカードが何なのか」しか分からないまま。

きわめて異様です。

どう考えても不可能です。

しかし「論理クイズゆえに正解がある」ということ前提を踏まえて、少しずつ思考を進めていきましょう。

ABとCの間にある最大の差異とは？

不均衡な配分

1〜7の数字が書かれた7枚のカードがある。
これをよくシャッフルして幼女ABCの3人に以下のように配る。

幼女Aにはカード3枚
幼女Bにはカード3枚
幼女Cにはカード1枚

「幼女AB」と「幼女C」の間には、「入手するカードの枚数」という決定的な差異があります。

幼女ABは、それぞれ「7枚のカードのうち3枚」が分かっている状態です。

しかし幼女Cは「7枚のカードのうち1枚」しか分からない状態。

情報量としては、圧倒的にABが持つ量の方が多いのです。

何とか、この辺りをうまく活用しなければなりません。

宣言内容

いったい、AとBはどのようなことを言ったのだろうか？

「事前打ち合わせができない」「暗号が使えない」「宣言以外のコミュニケーションができない」といった観点から、幼女ABの宣言内容は「誰にでも（Cにも）完璧に理解できる」ものでないといけません。

幼女Aの宣言は、BにもCにも伝わる。

そしてBには分かって、Cには分からないまま––。

普通に考えたら不可能です。

どうやら、何かしらのトリックが必要になりそうです。

ヒント

第1のヒント

本問には正解が存在する

するんですね。

聞いたらものすごく納得します。

ちなみに最初に答えを見た時は「分かるわけないです」って思いました。

第2のヒント

本問には別解が存在する

はい。

論理クイズとしては極めて珍しいのですが、この問題には正式に「これも正解である」と認められた別解が存在します。

それは「出題者が意図しなかった答え」。

気づかれた方もいらっしゃると思いますが、実は問題文に少々あいまいな部分があります。

そこをうまく活用すると、本来の答えとはかけ離れた（しかし正解である）答えが導き出されます。

論理クイズ史上に例を見ないレベルの盲点を突くポイントなので、気づくのはかなり難しいでしょう。

最初に別解を見た時は「どうしてこれで正解になるの？」って思いました。

この別解についてはとても面白い余談があるので、記事の最後でまるまる別章を設けて詳しく解説します。

「別解」についての記述は、今はここまでに留めます。

引き続き、「本来の正解」についてのヒントをお楽しみください。

第3のヒント

カードの数字が0〜6でも本問は成立する

きわめて大きなヒントです。

元々の問題では「0から6の数字が書かれた7枚のカード」でした。

「1,2,3,4,5,6,7」

「0,1,2,3,4,5,6」

共通しているのは？

第4のヒント

カードの数字は、「連続する7つの整数」である

はい。

ちょっとずつ、問題の全貌が見えてきました。

第5のヒント

数学系・IT系の人なら少し有利

問題文を
「全く同じ情報を受け取ってもBとCで得る情報が異なる」
と考えるのではなく、
「Bが「Aの発言」から引き出した情報を、Cは引き出せない」
と読み替えてみてください。

どこかで見たことはありませんか？

第6のヒント

幼女たちは、計算を行う

第7のヒント

幼女たちは、きわめて簡単な計算を行う

最後のヒント

割り算

正解

「自分のカードの合計値を7で割った余り」を宣言する

解説

導入：mod

本問では、解答にあたり「剰余つき除法計算（モジュラ計算）」という手法が必要になります。

何やら難しそうな単語ですが、実際にやることは「ものすごくカンタンな割り算」です。

––––いえ。
より正確に言うなら「ものすごくカンタンな割り算をして余りを出すこと」です。

「mod」という単語に「マインクラフトにおいて木を一発で破壊してくれる系の便利なアレ」というイメージ以外をお持ちの方なら、この時点で正解を看破されることでしょう。

私がPC版でMinecraftをプレイする理由はさておき、さっそくこの問題の解決に取り組んでいきましょう。

開始：ケーキ戦略

1から7までの数字が書かれたカード。

これらを全て合計した数字は？

1 + 2 + 3 + 4 + 5 + 6 + 7 =

28ですね。

「28」全体がケーキで表現されていると考えてください。

ケーキを3つの部分に––3人が持つそれぞれのカードの合計に比例したサイズに––分割されているとすると、3つのうち2つを知れば残りの1サイズの大きさを決定できます。

幼女Aが自分のケーキのサイズに関わる情報をBに伝え、それを活用してBが自分のケーキサイズの情報をもとにAのケーキサイズを算出すれば––––Cに知られることなくAはBに自分のケーキサイズを伝えられます。

逆もまたしかり。

ただし単に「私のカードの合計はN」と宣言するだけではダメです。

「私の合計は12」なら{2,3,7}や{3,4,5}といった組み合わせが複数ありますが、「私の合計が6」の場合は自らのカードが{1,2,3}と宣言しているようなものなので。

道具：剰余計算の一方向性

ここで登場するのが「余り計算」。

「余りを求める計算」というのは、代表的な「一方向性関数」です。

一方向性関数とは、「いったん計算したらその結果から元の数を求められない」という特性を持つ関数のことです。

例を挙げます。

5 + 3 = 8
6 – 3 = 3
4 × 3 = 12
などの足し算・引き算・かけ算は、
○ + 3 = 8
○ – 3 = 3
○ × 3 = 12
と一部を隠しても計算によって未知数を求められます。

しかし、
7 ÷ 2 = 3 あまり 1
○ ÷ 2 = ？ あまり 1
という割り算で余りを求める計算の場合、「割った数」と「余り」だけでは元の数を求められません。

いったん計算したら、結果から元の数を求められない。

この「一方向性関数」は、その情報の非対称性から公開鍵暗号方式などにも重宝されており、現代社会において必要不可欠な計算方式となっています。

この辺りの話は非常に面白いのですが長すぎるので、
「公開鍵暗号」
「RSA暗号」
あたりでググって終わらない夜のWikipedia旅に出てください。

進行：AとBの宣言

本問を解決するために幼女ABが宣言すべきこと。

それは、「自分のカードの合計値を7で割った余り」です。

これだけでABの両者は互いのカードが分かり、それでいてCは何一つ情報を得られないという状況が生まれます。

例を挙げましょう。
カードの配分が以下のような状態だとします。

A = {1,4,5}
B = {2,3,7}
C = {6}

Aのカードの合計値は1+4+5 = 10
それを7で割った余りは3

Bのカードの合計値は2+3+7 = 12
それを7で割った余りは5

Aは「私のカードの合計値を7で割った余りは3」と宣言することで。
Bは「私のカードの合計値を7で割った余りは5」と宣言することで。

Cに全く情報を与えないままABは互いのカードの内訳を把握できます。

ここで当然の疑問が生まれます。

なぜ、それだけで解決するのか？

カギとなるのは「割り算の余りを求める」という計算自体の特性、そして「Cが持つ1枚のカード」です。

発展：段階的に考える

先ほどと同じく、カードの配分は

A = {1,4,5}
B = {2,3,7}
C = {6}

であるとします。

さて、Aが
「私のカードの合計値を7で割った余りは3」
と宣言することでB（そしてC）はどのような情報を得られるでしょう？

1,2,3,4,5,6,7––––これらの数字を7で割った余りはそれぞれ1,2,3,4,5,6,0。

「7で割った余りが3になる」というカードの組み合わせは、{1,4,5}のほか{1,2,7}等も考えられます。

本問において「7で割った余りが○」というカードの組み合わせは無数に存在します。

その一覧を見てみましょう。

この表が本問のすべてと言っても過言ではありません。

よく見てください。

1から7までの全カードが、すべての「有り得るカードの組み合わせ」の各段につき2回以上登場しています。

ところで。

Aの宣言した「7で割った余りが3になる」という一文は、

「私のカードは
{1,2,7} {1,3,6} {1,4,5} {2,3,5} {4,6,7}
のどれかです」

という意味でしかありません。

これらは、カードの合計値を7で割った時に余りが3になるカードの組み合わせです。

そして重要なことに、1〜7までの全ての数字が必ず2つ以上の組み合わせに出現します。

この時点で、BもCも、「Aのカードの組み合わせは上記のうちどれか」ということを知ります。

{6}のカードを持っているCは
「Aのカードは{1,2,7} {1,4,5} {2,3,5} のどれか」
だと分かります。

ところが、カードを1枚しか持たないCに分かるのはそこまで。
「Aのカードは{1,2,7} {1,4,5} {2,3,5} のどれか」
という組み合わせはある程度まで限定できますが、実際にAが持っている可能性のあるカードは{1,2,3,4,5,7}のいずれか。

よく考えてみると、Cにとって「実際に誰が何のカードを持っているのか」という情報は一切増えていません。

もうちょっと詳しく考察してみましょう。

Aが「合計を7で割った余りが3」
Bが「合計を7で割った余りが5」

と宣言したことで、それぞれのカードの組み合わせは絞られました。

さて、ここからCが持つ「6のカード」を含む組み合わせを排除する（下表赤字）と、C視点では以下のようになります。

C視点で、正解は

の3パターンのうち、いずれかである––ということは分かります。

ですが、分かるのはそれだけ。

つまるところ「AもBも”1,2,3,4,5,7″のカードのうちどれか3枚を持っている」という開始時の状況からCの情報はそれほど増えていません。

すなわち、可能性のある「組み合わせ」までは分かりますが、「実際にAとBが何のカードを手にしているのか」をCが特定することは不可能なのです。

では、同じ情報を聞いているBはどうなのでしょう。

Bは、Cと違って3枚のカードを保持しています。
そのため、Aの発言によって消去できる可能性がCよりも増えます。

{2,3,7}を持つ幼女Bは、Aの宣言から以下の可能性を排除できます。（下表赤文字）

他の有り得るすべての可能性が排除されたこの瞬間、BはAのカードが{1,4,5}であると気づきます。

以上のように「自分のカードの合計を7で割った余り」を伝えるだけで、AとBは、Cに「実際に誰が何のカードを持っているのか」という情報を一切与えることのないコミュニケーションが可能になるのです。

応用：クールなBの宣言

少し考えてみると、Aが宣言した時点でBはすべてのカードの内訳を把握することになります。

なので、Aが「自分のカードの合計を7で割った余りは3」と言ったあと、Bは「Cのカードは6」と宣言しても正解になります。

これでもAはBのカードが何なのか分かりますし（自分のカードでもCのカードでもないものがBのカード）、何よりBは余計な情報（自分のカードの組み合わせ）をCに与えない分、よりクールな答え方になります。

応用2：クールなCの思考

ちなみに。

問題の本筋とは関係のない余談になりますが。

Aが「合計を7で割った余りが3」と宣言した時点で、Bが発言する前に、Cには「Bのカード合計を7で割った余りは5である」ということが分かります。

なぜか。

「全カードの合計値28を7で割った余りは0」です。

「Aの余りは3」。
「Cの余りは6」。

つまり「Bの余り」は、「ACの余り9(=余り2)」を0にするものでなければならないはずです。

「合計を7で割った余りが3」
「合計を7で割った余りが6」

ここに

「合計を7で割った余りが5」

が加われば、

「合計を7で割った余りが3+6+5 = 14」

となり、これは

「余り14 = 7で割り切れる = 余り0」

を意味するので、Aの発言だけでCはBの発言を事前に知ることができるのです。

まあ。
Cに知ることができるのはその情報だけで、AとBのカード内容が分かるわけではないのですが。

補足：よりシンプルでスマートな「別解」

経緯

さて、記事の途中で述べた「別解」について触れましょう。

「7で割った余り」を用いるのが出題者の意図した「正解」でした。

しかし、問題文のある箇所に不備……というかスキ……というか少々あいまいな部分があり、多くの参加者はそれを活用した（スマートな）解答を書きました。

いろいろありましたが、最終的にこの「別解」は「これも正解として認める」という結論に落ち着きました。

その正解とは？

驚愕の正解

カードの配分が以下のような状態だとする。

A = {1,2,3}
B = {4,5,6}
C = {7}

Aは「私かBのどちらかが1,2,3のカードを持っている」と宣言する。
Bは「私かAのどちらかが4,5,6のカードを持っている」と宣言する。

Cは、ABが何のカードを持っているのか分からないままである。

絶句する解答

何が起こったのか理解しがたい状況です。

「真実」を述べねばならない幼女Aが「私かBのどちらかが1,2,3のカードを持っている」と宣言した––––。

どう考えても、誰から見ても「幼女Aが1,2,3のカードを持っている」と一瞬でバレてしまうのは明らかです。

なぜこれが正解になるのでしょう？

きわめて純粋に論理的な何か

議論のマトになったのは、問題文の以下の部分です。

まず、幼女Aは自身のカードを見て、何らかの「真実（であると認識していること）」を宣言する。

続いて、幼女Bも自身のカードを見て、何らかの「真実（であると認識していること）」を宣言する。

原文における
“Player A looks at his cards and makes a statement that he knows to be true.”
（プレイヤーAはカードを見て、真実であると認識していることを宣言する）
という箇所です。

ABの発言をもう一度見てみましょう。

A：「私かBのどちらかが1,2,3のカードを持っている」
B：「私かAのどちらかが4,5,6のカードを持っている」

これらの発言は、いずれも間違いなく真実です。
Cが7のカードを持っているという条件付きで。

この時、幼女Cからすると––––きわめて論理的に考えると、AとBのどちらが{1,2,3} {4,5,6}を持っているのかが、

分かりません。

両者の発言は「AとBのカードはCが持っていないカードである」という完全に真実を述べているものであり、その発言だけを切り取った場合、究極的に論理的な観点からするとCにはそれ以上の情報が与えられません。

もちろん、普通に考えたらAの「私かBのどちらかが1,2,3のカードを持っている」という発言は、Aが実際に{1,2,3}のカードを持っていないと言えないはずです。

しかし––––思い出してください。

問題文によると、幼女ABが述べるのは「真実」ではなく「真実であるとその幼女が認識していること」です。

実際にABの発言は真実ですし、どんな状況下でも誰しもが「Aが{1,2,3}を持っている」と看破できます、が、「発言内容を幼女が正しいと認識しており、実際に発言が真実である」ので、その発言に至る途中経過が問題にならなくなり、幼女Cは「Aが{4,5,6}、Bが{1,2,3}を持っている」という（常識で考えたらありえない）（しかしものすごく厳密に言うと論理的にはありうる）可能性を排除できる機会を失ってしまう––––

––––のではないか、つまりこの方法でもきちんと題意を満たしている、という観点からこの別解が（多くの参加者）によって提示されました。

もし問題文が「幼女ABは自分のカードに関する真実を述べなければならない」だったら、この別解は生まれなかったでしょう。

シンプルな例で別方面から考える

感覚的に納得しにくいポイントなので、簡単な例で考えてみましょう。

「1,2,3の数字が書かれた3枚のカードを用いるバージョン」を想定します。

Aには「1」のカード
Bには「2」のカード
Cには「3」のカード

がそれぞれ配られたとします。

この時、Cには「誰が1のカードを持っているのか」「誰が2のカードを持っているのか」が分かりません。

さて、Aは次のように発言します。

A「私かBのどちらかが1を持っている」

この発言は紛れもなく真実です。

さて、ここで「1を持つAに可能な（真実の）発言」4パターンを考えてみましょう。

#1. 私のカードは1
#2. 私のカードは1または2
#3. 私のカードは1または3
#4. 私のカードは1または2または3

言うまでもなく#1はルール違反（Cにカード内訳が伝わってしまう）です。

#4は誰にも何の情報も伝えていません。

つまりAの発言は、#2と#3のどちらかでなければいけません。

しかし、AからするとBのカードが何なのか分からないので、#2と#3のどちらが「Bに伝えるべき正しいメッセージ」なのか分かりません。

Bが2を持っている今回の場合は「#2. 私のカードは1または2」と発言すればCに情報を与えないままBに情報を伝えられるのですが、そのためには発言前にBのカードが何なのか分かっていなければならないのです。

結果的にAは#2も#3もどちらも発言できません。

つまり、実質的には「私は1を持っている」という宣言とほぼ変わらない「私かBのどちらかが1を持っている」という発言だけが、「真実である」という条件を満たし、かつ「2を保持するB」にのみ情報を与えられる唯一の宣言なのです。

それがCにも正解を与えてしまうかどうかの議論は別として。

論理って　　面白

かなり高度な意味論・論理学にも踏み込んで議論されたこの「別解」に関する問題は、「まあ問題文がちょっとあいまいだったよね」ということで前述の通り「別解も正解とする」という判断が下され決着がつきました。

一見するとどう考えても不可解な答えが正解になる。

「論理」とは、かくも面白い要素の集合体なのです。

まとめ

ここまでお読みいただきありがとうございました。

この論理クイズが、混迷する現代社会を生き抜く方々の清涼剤となりますように。

参考

Moscow Math Olympiad Puzzle

140字以内の問題文

1〜7の数字が書かれた7枚のカードをランダムにABCに配る
Aは3枚、Bは3枚、Cは1枚を受け取る
AとBは1回ずつ「真実であること」を全員に聞こえるよう宣言し、互いに全員のカードの数字を把握したが、Cだけは何も分からないまま（C自身の数字しか分からないまま）だった
AとBの発言とは？