パズルの国のアリス

集え! 賢者たちよ(解答)

坂井 公(筑波大学) 題字・イラスト:斉藤重之

 まず最初にお詫びを申し上げたい。5月号の誌面で,Eが「わかりました。22です」と述べた部分は誤りで,これでは解答が得られない。数値を間違えてしまい,解く努力をなさった読者には大変申し訳なく思っている。ここでは数値を「26」に訂正して解答を書かせていただきたい。

 どの問題も「知っている」あるいは少なくとも「類似の問題を見たことがある」という読者が少なからずおられるだろう。そのような読者諸氏には申し訳ないのだが,初めてこの種の問題をご覧になる人のために少しゆっくりと解説していきたい。

 特に最初のウォーミング・アップの問題は,帽子の色を当てる形,あるいは汽車の煙で顔が汚れる話の形でよく出題される有名なものである。設定が微妙に違うこともあるが問題の本質は同じで,共通知識を利用するパズルの典型といえるので,この種のパズルを語る場合に外すことができない。

 では,解答である。この種の問題に慣れていないと奇妙に聞こえるだろうが,Cが「わかります」と答えるのは当然で,実はAとBの「わからない」という返答こそ重要だ。これは,「少なくとも1人は偶数」という部屋全体で共有される知識が大きく作用するせいで,この知識を梃子として各人の推論が進んでいく。まず,Aが「わからない」と言ったことの意味だが,それは「BとCの帽子の少なくとも一方は偶数だ」と言ったのと同じである。なんとなれば,もし両方とも奇数なら,少なくとも1人は偶数という知識から自分の帽子の番号が偶数とわかるからだ。次に,そのあとでなされたBの「わからない」という発言は「Cの番号は偶数だ」と言ったのと同じである。なんとなれば,「BとCの一方は偶数だ」と知ったのちは,もしCが奇数なら,当然自分が偶数だとわかるはずだからだ。こうして,Bの発言ののちは,誰でもCの帽子が偶数とわかる。当然C自身にもわかる。一方,AーBーCの番号が,奇ー奇ー偶,奇ー偶ー偶,偶ー奇ー偶,偶ー偶ー偶のいずれだったとしても,A,B,Cの返答は順に「わからない」,「わからない」,「わかる」になるから,AとBの番号について言えることは何もない。面白いことに,AやBの返答の一方が「わかります」だったとしても,Cの返答は「わかります」になる。ただし,その場合は,Cの帽子は奇数であり,AやBの番号の奇偶性がわかることもあることを確認されたい。

 次の問題は,上の問題の発展形に過ぎないが,こちらは40人が妻の不貞を見つけるという形で出題されることが多いようだ。ここでも共通知識は「少なくとも1人の番号は偶数」ということである。仮に部屋に偶数番号の人が1人しかいなかったらどうなるだろうか。その人は,自分以外が全員奇数なのを見て,「少なくとも 1人いる」と言われた偶数番号が自分であることがわかるから,ただちに「わかった」と言うであろう。では,2人いたらどうだろうか。その場合,その2人は,自分以外の人の中に偶数番号がちょうど1人いることを知っている。そこで考えることは「もし自分が奇数だったら,部屋には偶数番号が1人しかいないから,その人はただちに『わかった』と言ったはずだ。そうでないから自分は偶数に違いない」となる。そこで2回目にきかれたとき,その2人は「わかった」と手を挙げる。その先は,数学的帰納法だ。部屋に偶数番号がn人いたとき,そのn人はn回目に「わかった」と手を挙げるとしよう。すると,n+1人いた場合,そのn+1人は自分の外に偶数がn人いるのを見て次のように考える。「もし自分が奇数だったら,部屋には偶数番号がn人しかいないから,その人たちはn回目に『わかった』と言うはずだ。そうでないから自分は偶数に違いない」。そこでn+1回目に聞かれたとき,そのn+1人は「わかった」と手を挙げる。結局,20回目に挙がったのだから,手を挙げたのは20人のはずだ。その偶数番号20人の中に手を挙げなかった人がいれば,その人はもちろんコンテストに落第である。

 3番目が,先月の問題の中では比較的目新しいかもしれない。類似の問題は見たことがある人も少なくなかろうが,一応,筆者がこのコラムのために作ったものだ。もちろん,原理は他の問題と変わらない。今度の共通知識は,「3人のうち,2人の番号の和がもう1人の番号」ということだ。この場合に,順繰りの返答からその場にいない第三者にわかることは,3人の番号の比だけだ。D,E,Fの番号の比をdefと書くことにすると,これはもちろんすべて整数の比だが,最初のDの返答から何がわかるだろうか。実はdef≠2:1:1がわかる。なぜならEとFが同じ番号nならば,共通知識よりDの番号は0または2nでなければならないが,番号はすべて正の整数ということだから2nでなければならず,Dには自分の番号がわかる。Dが「わからない」と答えたからには,その可能性はない。

 さて,問題設定よりdefは正の整数比でdefefdfdeのいずれかが成り立つ。また,defは互いに素であるとしてもよいこと,その場合defがただ1つに定まることは理解していただけるだろう。ここで,順繰りにきいていけば最大の番号を持つ人がやがて「わかった」と言うであろうことを,数学的帰納法で一足飛びに証明してしまおう。まずdefの最大値が2であれば,他の2つは1であり,その場合最大の番号を持つ人がきかれた最初の時点で「わかった」ということは,先と同じ論法により明らかである。今,仮にdefとすると,Dにはenfnという番号が見えるのだから,自分の番号が(efnまたは(efnであることがわかる。従って,比はefefまたはefefであり,もし後者であれば帰納法の仮定により,Eがある時点で「わかった」と言うはずだ。したがって,その時点を過ぎてもEが「わかった」と言わなければ,自分の番号はEとFの番号の和であることがわかり,次に自分がきかれた番で「わかった」と言うことができる。この事情は,最大の番号を持つ人がEやFであっても同じである。

 これでこの問題の一般論は完成である。しかし,具体的な比の場合に何回目に「わかった」と言うかは,順次考えていったほうが近道だろう。Dに続くEの「わからない」という返答からは,比1:2:1,2:3:1の可能性が除ける。後者が除けるのは一般論で述べたように,Dが「比は2:1:1でない」と言ったのも同然だからだ。同様に次のFの返答により,1:1:2,2:1:3,1:2:3,2:3:5の可能性が除ける。さらに,Dの2回目の「わからない」により,3:2:1,4:3:1,3:1:2,4:1:3,5:2:3,8:3:5の可能性がなくなる。最後にEがとうとう「わかった」と言ったわけだが,この結果,比の可能性には1:3:2,2:5:3,1:4:3,2:7:5,3:4:1,4:5:1,3:5:2,4:7:3,5:8:3,8:13:5の10通りがありうる。その場にいない第三者には,一般にはこのように比の可能性のいくつかがわかるだけだが,Eが26と答えたとすれば,上の10通りのうちEの比率が26を倍数に持つのは8:13:5だけだということにより,Dの番号は16,Fの番号は10だとわかる。

 最後の問題は,少なくともその変形が色々なところで引き合いに出されるから,詳しい読者は当然知っておられよう。実は,本コラムの前身の「数学ゲーム」でもガードナーが紹介している(『サイエンス』1980年2月号,別冊サイエンス『数学ゲームIV』)。そのような古いパズルをあえて載せたのは,やはり,これが共通知識パズルの名峰の1つであり,知らない読者もおられるだろうから,考えていただくのも悪くないと思ったからだ。共通知識は「2以上100以下の2つの整数abの和abと積abがそれぞれ2人の番号」ということだ。一応確認しておくが,2つの数abがわかれば当然ababもわかるし,逆にababがわかれば, 2次方程式x2−(abxab=0を解くことでabもわかる。

 積pabが見えているはずのSに和がわかるのは,pを2以上100以下の2つの整数の積に表す方法が1通りしかない場合だ。分析すると,これにはpが,2つの素数の積の場合,50より大きい素数(例えば53)を因子に含む場合などがある。すると,和sabが見えているPの言葉「Sに和がわかる可能性はない」は,「sが2つの素数の和でなく55以上でもない」ことを含意する。この結果,sの可能性として残るのは,11,17,23,27,29,35,37,41, 47,51,53だけとなる。しかも,このうち51は候補から落ちる。なぜなら51=17+34だからp=17×34の可能性があり,このpを2以上100以下の2つの整数の積に表す方法は他にないので,この場合Sには和が51とわかるからだ。

 次に,この言葉をきいてSに和がわかったということは積pの因数分解abのうち,abが上の10候補のどれかになるのが,ただ1つの場合である。例えばp=18は, 2×9と3×6の可能性があるが,後者は3+6=9が候補の中にないので, s=2+9=11とわかる。また,p=24は,3×8,6×4,12×2の可能性があるが, 6+4=10も12+2=14も候補にないので,やはりs=3+8=11とわかる。反対にp=30は,2×15,3×10,5×6の可能性があり, 2+15=17も5+6=11も候補の中にあるので,Sには和がどちらかわからない。

 最後にSに和がわかったということから,Pにも積がわかったという事実がある。これは,分割sabが上の18や24のような積pabを生み出す場合が1通りしかないことを意味する。上で見たように,s=11は,3+8の場合にp=24,2+9の場合にp=18を生み出し, Sに和がわかったという事実をもってしても,この区別がつけられないのでPには積pを決定するすべがない。同様に考えていくと, s=17は,13+4のときにのみ,上のような積p=13×4=52を生み出す。従ってs=17,p=52の場合,問題のような会話が起こりうる。詳細は読者に検討を願うしかないが,そのような会話が起こりうるのはこの場合だけなので,Sの番号は17,Pの番号は52であったことが,第三者にもわかる。

 2つの数abの上限を上げていくとどうなるか気になる読者もおられるだろうが,これ以上は計算機実験の領域に入るので,適当な文献を参照されるのが望ましい。筆者の知るところではジュリアン・ハヴィルの『世界でもっとも奇妙な数学パズル』(青土社,松浦俊輔訳)が第3章でかなり詳しく論じている。

参考にした本
Mathematical Puzzles:A Connoisseur's Collection(2004),
Mathematical Mind-Benders(2007) P. Winkler。
邦訳は『とっておきの数学パズル』(2011年),『続・とっておきの数学パズル』(2012年),ピーター・ウィンクラー著,坂井公・ 岩沢宏和・小副川健訳,日本評論社。

問題はこちらです