パズルの国のアリス

トランプ兵士たちの相愛図(解答)

 グリフォンのつぶやきは,グラフ理論におけるマンテルの定理を根拠にしたものだ。その内容は「頂点数nの無向グラフが3角形を含まないとき,グラフの辺数は以下である」というものだが,これを兵士の相愛関係に翻訳すれば「n人の兵士の中に仲良し3人組が存在しなければ,仲良しペアはせいぜい組しか存在しない」ということになる。なお,無向グラフとは頂点と辺により構成された“ふつう”のグラフ(一方,頂点と,向きを持つ辺で構成されたグラフは有向グラフという)。また,x以下の最大の整数を表す。

 従って,いま兵士の数は40人だから,仲良し3人組が存在しなければ,仲良しペアの数はせいぜい=400組ということになり,401組はそれよりも多いから,仲良し3人組が必ず存在する。

 この定理は,仲良し3人組ができないようにして仲良しペアをどこまで増やせるかを考えていくと,自然に思いつくだろう。というのは,n人を2つのグループAとBに分けて,AB間ではみな仲良しだがAどうしやBどうしでは仲良しペアが存在しない(グラフ理論でいうところの完全2部グラフ)という状況を考えると,この場合に仲良し3人組が存在しないことはすぐに了解されよう。しかし,これにさらに仲良しペアを増やそうとするとAどうしまたはBどうしを仲良くさせるしかないから,仲良し3人組が形成される。n人をグループAとBに分けてAB間ペアをなるべく多くするには,ほぼ同数に分けるのがよいので,その場合にペア数の上限が達成される。

 だが,どんな状況下でもペア数がよりも多いと仲良し3人組が必ず存在するということは,それほど自明ではない。その証明は複数知られているが,それぞれ特長があるから,そのいくつかを紹介しよう。

 まず,一番シンプルで多くの人が考えつきそうな証明は,数学的帰納法によるものだろう。

n=3, n=4のときはそれぞれ=2,=4だが,この場合は仲良し3人組が存在することは相愛図を描けば明らかだ。n≧5としよう。兵士uと相愛の兵士の数をdu) と書くことにする。仲良し兵士のペア{ab}を任意に選ぶ。ab以外の兵士の全体をVとすればその総数はn−2である。da)+db)≦nならば,Vどうしの間の仲良しペアの数e

となり,帰納法の仮定によりVの中に仲良し3人組が存在する。da)+db)>nならばaまたはbと相愛のVの兵士の数は延べn−2人より多くなる。よって,だれか1人cVabの両方と仲良しであり,{abc}が仲良し3人組を形成する。

 やや技巧的だが,帰納法を使わない証明があるので,そちらも紹介しよう。n人の兵士の集合Vが仲良し3人組を含まないとする。仲良しペア{uv}の全体をEとし,その要素数#Eeとする。仲良し3人組が存在しないという条件から,uvが相愛のとき,uvの双方と相愛の兵士wVは存在しないから,du)+dv)≦nである。よって

である。なお,等号の右辺では各du)がdu)回加算されているので,左辺のdu2の和と等しい。両辺にnをかけ,コーシー・シュワルツの不等式を用いると

であり,n2/4≧eが示される。

 以上2つの証明は,du)を頼りにするもので,帰納法とコーシー・シュワルツの不等式などの違いはあれど,同趣向といえよう。しかし,次の証明は意表をつくものではないだろうか。

 n人の兵士の集合Vに仲良し3人組は存在しないとして,仲良しペアの数をeとする。それぞれの兵士vに非負の実数wv)を重みとして付け,

という条件下で,総合相愛度

という量を最大化することを考えてみよう(Eは仲良しペア{uv}の全体)。兵士aと相愛の兵士たちの重みの総和をSaと書く。すなわち

abが仲良しペアでない,すなわち{ab}∉Eとすると,

 SS′+waSawbSb

と書ける。ここでS′はabを除く兵士たちに関する総合相愛度である。ab以外の兵士の重みを一定とすると,S′,SaSbwa)+wb)はすべて一定だから,SaSbのときにSの値を大きくするには,wb) を0とし,wa)をなるべく大きくするのがよい。ということは,Sが最大化されていたとしたら,そのときのwv)は2人の兵士を除いて全員0と考えてよいということだ。なぜなら,もし重みが0でない兵士が3人以上残っていたとしたら,その3人の中には相愛でない2人が存在する。そして,その場合,その一方からもう一方へすべての重みを移し替えても,少なくともSが小さくなることはないからだ。こうして,Sが最大化されていたとしたら,重みが正の兵士は2人しかいないと考えてよく,その2人は仲良しでかつ重みがともに1/2のときにSは最大の1/4になる。一方,すべての兵士に1/nの重みを付けるとSe/n2となるが,もちろんこれは最大の場合の1/4を超えることはないから,en2/4が示された。

 最後の問題,すなわち,仲良しペアが401組存在する場合に仲良し3人組が1組どころではなく20組以上存在することを示すには,マンテルの定理を次のように強化するのが近道だろう。兵士の相愛関係に翻訳すれば,「2n人の兵士集合Vn2組よりも多くの仲良しペアを含むなら,Vにはn組以上の仲良し3人組が存在する」というものだ。この証明もいろいろとありえそうだが,筆者には,地道な帰納法による次のものしかすぐには思いつかなかった。

 n=2のときは相愛図を描けば明らかだ。2≦nkのときに正しいとして,nk+1とする。マンテルの定理より仲良し3人組が存在するので,そのような3人abcVを任意に取り,Vからabcを除いた集合をV′(つまりV′=V\{abc})とすると,その兵士の数#V′は2nー3=2kー1である。

 da)+db)+dc)≧3k+5ならば,{abc}とV′の間に3kー1組以上の仲良しペアが存在するからabcのうち2人以上と仲良しペアを作る兵士vV′が延べk人以上存在し,それぞれがabcのうちの2人と仲良し3人組を形成する。よって,{abc}と合わせて全部でnk+1組以上の3人組が存在する。

 da)+db)+dc)≦3k+4の場合,da)≦db)≦dc)としても一般性を失わない。このとき,da)+db)≦2k+2。よって,V′′=V\{ab}とするとV′′内の仲良しペアの数eは,

en2ー(da)+db)ー1)≧(k+1)2ー(2k+1)=k2

を満たすから,帰納法の仮定よりV′′には仲良し3人組がk個以上存在する。よってVには{abc}と合わせてnk+1個以上の仲良し3人組が存在する。

 実は,マンテルの定理をさらに一般化したテュランの定理というものがある。それを兵士の相愛関係として述べると「n人の兵士グループVに仲良しk人組が存在しないとしたら,仲良しペアの数eは高々

だ」となる。なお,rn mod(kー1)である。k=3の場合,上の式はと等しくなる。総合相愛度を用いた論法により,

は簡単に導かれるし,rの項がついている場合も帰納法によるマンテルの定理と似た証明が可能だが,細部は読者にお任せしよう。

問題はこちらです