パズルの国のアリス

ヤマネの姪たちの習い事(回答)

 最初の問題は,いささか厄介なので,後の問題を先に片づけることにしよう。全部で7種類の習い事がある場合,どの2匹をとっても,共通の習い事がただ1つある状況を作れるかという問題だ。ただし,全員がやっている習い事はないし,1匹で7種すべてを習っていることもないとする。実は,そのような状況は,n種の習い事があってn人いる場合に一般化しても,簡単に作れる。例えば,ある1つの習い事を1人(Aとする)を除くn−1人全員がやっていて,残りn−1の習い事をAと他の1人だけがやっている場合である。

 ヤマネの姪たちの場合に適用すると,例えばピアノはサンデイを除く全員が習っていて,バイオリンはサンデイとサタデイ,水泳はサンデイとフライデイ,絵画はサンデイとサーズデイ,珠算はサンデイとウェンズデイ,書道はサンデイとチューズデイ,ダンスはサンデイとマンデイが習っているならば,フライデイが語っているような状況になるし,どの2匹をとっても共通の習い事は1つだけになる。

 しかし,それに加えて「どの習い事をとっても,それをやっている子が3匹以上」という状況を作るのはそう簡単ではあるまい。いささか天下り的だが,下の表のように習い事を割り振ると,その状況になる。表の○はその習い事をやっていることを示し,×はやっていないことを示す。例えばフライデイはピアノ,バイオリン,水泳を習っていて,他は習っていない。

 上の表からは規則性が感じられないかもしれないが,実は,やみくもに作ったものではなく,有限幾何の理論で知られるファノ平面を利用したものだ。この解答で有限幾何について詳しく解説することは無理であるから,興味を持った読者は上記の言葉や「デザイン」,「有限射影平面」というようなキーワードで書物やインターネット情報を検索してみられるとよいだろう。少しだけ薀蓄を述べると,ファノ平面のような有限射影平面を利用すると,n=7以外にも,n=1+kk2kが素数pの冪(べき)の場合には必ず下のような表を作ることができる。その結果,「どの2匹をとっても共通の習い事が1つだけあり」,かつ「どの習い事をとっても,姉妹7匹のうちにそれをやっている子が3匹以上いる」というだけでなく,「どの2つの習い事をとっても,その両方を習っている子がただ1匹いる」という状況を作り出せることがわかっている。

 さて,最初の問題に戻ることにしよう。もし,ダンスという習い事がなければ,上のどちらの例でもサンデイとマンデイには共通の習い事はなくなってしまう。かといって,その代わりにマンデイにサンデイの習っている他の習い事の1つを習わせたりすると,他の姉妹との共通の習い事が2つ以上になってしまう。従って,要求された状況を達成しようとすると,習い事が7種類以上は必要に思える。それを証明するのが課題だ。これについては『天書の証明』(アイグナー/ツィーグラー著,蟹江幸博訳)にあるものが見事なので,それを紹介しよう。

 一般化して,どの2人も共通の習い事を1つだけ持つようにするには,習い事の数は生徒たちの数以上でなければならないことを示せばよい。生徒たち全員の集合をX,習い事全体の集合をAとする。上の条件下で#A<#Xだとし(集合Sの要素数を#Sと表す),矛盾を導けばよい。xXがやっている習い事の全体をAx(⊂A)とすると,前提条件から2≦#Ax<#Aであることはすぐわかる。aAを習っている生徒の集合をXaとすると,xaを習っていない場合,#Ax≧#Xaであることが次のようにしてわかる。yXaを任意に取ると,条件よりxyの共通の習い事ax,y(≠a)がただ1つ存在するが,当然ax,yAxである。また,異なるyzXaについてax,yax,zbということはありえない。なぜなら,abの2つがyzの2人の共通の習い事になり条件に反するからだ。従って,xaを習っていないなら,#A・#Xa<#X・#Axとなり,#A(#X−#Xa)>#X(#A−#Ax)となるが,

であるから矛盾する。

 『天書の証明』には,さらに短い別証明も載っている。この方が見通しはいいのだが,線形代数の知識が必要なので,そういうことに強い読者のために概要だけを紹介しよう。縦軸に生徒たち,横軸に習い事をとり,ある生徒がある習い事をしているかどうかを0と1で表した行列をMとする。左下の表でいえば×を0,○を1で置き換えた行列で,組合せ論やグラフ理論では「生起行列」,「結合行列」などと呼ばれるものだ。Mの転置行列をMとし,NMMを考える。少し考えればわかることだが,Nxy成分Nxy](xyXxy)はxyの共通の習い事の数だし,Nの対角成分Nxx]はxの習い事の数#Axにほかならない。従って,条件を満たせばNの対角成分は2以上の整数で,他の成分は1である。このような行列Nは正定値であることがすぐにわかり,従って正則だからその階数は#Xである(対称行列が正定値であるとは,固有値がすべて正の実数になることと同値である)。当然Mの階数も#X以上でなければならず,その列数,すなわち習い事の数#Aも#X以上でなければならない。

問題はこちらです