パズルの国のアリス

兵士たちの大喧嘩(解答)

 最初の問題は,グラフ理論で「ディラックの定理」と呼ばれている事実から材料をいただいた。余談だが,この定理のディラック(Gabriel Andrew Dirac)は有名なノーベル賞物理学者(Paul Dirac)ではなくその継子で,母の再婚によりそういう姓になったらしい。また母はノーベル賞物理学者のウィグナーの妹だそうだから,大変な学者一家の出である。

 さて,ディラックの定理は40人でなくとも一般に偶数人の円卓において成立するもので,グラフ理論の言葉で表現すると「2n個の頂点を持つ単純グラフにおいて,どの頂点の次数もn以上ならば,そのグラフにはハミルトン閉路が存在する」となる。単純グラフ,次数,ハミルトン閉路などの用語が聞きなれないという読者がおられるかもしれないが,いずれも基本的な用語なので適当な教科書を参照されたい。

 さて,座席表作成の手順であるが,最初は兵士たちを勝手な順番でぐるりと配置する。その結果,仲の悪い兵士が隣り合っているとし,その2人を時計回りにA0,B0としよう。さらにB0から時計回りに進みA0に戻るまでB0と仲の悪くない兵士を順にB1,B2,……,Bkとする。B0と仲の悪い兵士は19人以下だから,k≧20だ。Biの右隣の兵士をAiとする(Ai=Bi−1ということもありうる)。A0と仲の悪い兵士も19人以下だから,A1,A2,……,Akの中にはA0と仲の悪くない兵士Ajがいて,Aj≠B0だ。そこでB0から時計回りにAjまでの兵士の全員をこれまでとは完全に逆順の席にする。この操作を行った結果,A0-B0,Aj-Bjという隣接関係が解消され,代わりにA0-Aj,B0-Bjという隣接関係ができるが,他の隣接関係は保ったままだ。新しくできる隣接関係はどちらも仲が悪くないから,A0-B0が消えたことで,仲の悪い隣接関係は確実に1つ(場合によっては2つ)減る。こうしてこの操作は,仲の悪い隣接関係を減らしていくから,やがてそのような関係はゼロになり,目標が達成される。

 今の議論を少し精密化すると,グラフ理論で「オーレ(Ore)の定理」と呼ばれているものにたどり着く。これは「頂点数nの有限単純グラフGにおいて,頂点vの次数をdeg(v)と書く場合に,隣接しない任意の2頂点vwについてdeg(v)+deg(w)≧nが常に成立するなら,Gにはハミルトン閉路が存在する」というものだ。ハミルトン閉路の構成方法も上の議論と基本的に同じだから,あとは読者に考えていただこう。

 2つめの問題もグラフ理論の用語で表現できる。「有限単純グラフの頂点をn色で塗り分けるとき,どの頂点もせいぜいその隣接頂点の1/nとしか同色にならないようにできるか?」というものだ。

 この答えも,実際に贈り物配布表の構成手順を示すのが実用的だろう。贈り物の種類をK1,K2,……,Knとし,最初は好きなように客に配ってみよう。この時点では全員に同じものを配るというのでもかまわない。客の1人Pを取り,その知り合いの全体をF とする。そのうちで贈り物Kiを配られた客の全体をFi)とすると,もちろんF(1),F(2),……,Fn)はFの分割になる。Pに配られた贈り物がKjであり,#Fj)>(#F)/nであるとしたら,ある贈り物Kiij)で#Fi)<(#F)/nとなるものが存在する(#Xは集合Xの要素数を表す)。このようなときにはPへの贈り物をKjからKiに変えることにする。問題の条件を満足しない客がいる限り,このような贈り物の変更を繰り返すことでやがて条件が満足されることを示そう。つまり,こうした贈り物の変更は永遠には続かないことを証明すればよい。

 そのためには同じ贈り物をもらった知り合いペアの総数について考えるとよい。上の贈り物の変更操作で,変更前はFj)の全員とPとがペアを作っていたが,変更後はそれらのペアが解消されてFi)の全員とPとが新しくペアになるものの,他のペアには影響がない。#Fj)>#Fi)だから,ペアの総数は確実に減るが,もちろん非負の整数値だから,ある一定の値未満になることはない。よって,贈り物の変更が永遠に続くことはない。

問題はこちらです