コンピュータ計算による網羅的な探求の例としては，以下の２つの有名な極値問題が解決されたことがあげられる．

(1)１９８８年，ヘールズはケプラーの球の詰め込み問題（１６１１年）が正しいことを示した．

(2)１９７６年，ハーケンとアッペルは４色問題（１８５２年）が正しいことを示した．

　４色問題（平面上の地図を塗り分けるには４色が必要かつ十分である）は素人でも理解できる問題である．見た目には簡単には思えるが，実は容易に解ける問題ではなく，多くの間違った証明を生み出し，失敗と部分的解決が繰り返されてきた悪名高い問題であるが，かくして４色問題は４色定理となった．

　今回のコラムでは，地図が２色で塗り分けられるための必要十分条件を見いだす問題＝２色定理を取り上げることにする．２色問題は地図塗り分け問題の特別な場合にあたるのである．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【１】２色問題

　紙の上に鉛筆で閉曲線を描く．その際，自分自身と交差すること，また，交点では２個以上の弧が交わってもよいことにする．次に，閉曲線から得られた地図に色を塗るのだが，ある国を黒く塗りつぶし，国境線で隣り合う国はそのままにしておく．

　その結果は市松模様となるが，これは偶然ではない．この事実を初めて知ったのは高校生のときであるが驚き，そして不思議に思ったものである．

　しかし，２色定理の証明はあっけないほど簡単である．どの隣接する２面も同じ色でないように，白と黒の市松模様に塗ることができるためには，１の頂点で偶数の面が交わらなければならない（＝頂点の次数はすべて４以上の偶数）ことに気づきさえすればよい．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【２】２色定理の応用

（問）３種類の平面充填形，正三角形（３，６），正方形（４，４），正六角形（６，３）のうち，どの隣接する２面も同じ色でないように，黒と白の市松模様に塗ることができるのはどれか？

（ヒント）これが可能なためには，１つの頂点で偶数の面が交わらなければならない．すなわち，（ｐ，ｑ）においてｑは偶数．

　球面，トーラスなどの一般の曲面に対しても，２色塗り分け可能であれば，頂点の次数はすべて４以上の偶数である．

（問）５種類あるプラトン立体のうち，どの隣接する２面も同じ色でないように，黒と白で塗ることができるのはどれか？

（答）正八面体

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【３】市松モザイク模様

　以上は，平面（空間）を合同な多角形で埋めることを考えたものですが，次に，三角形Ｐ（黒塗り）とそれを裏返した三角形Ｑ（白塗り）の２つを交互に並べて，平面全体をタイル張りすることを考えます．たいていの場合は途中でタイル同士が重なってしまいますが，うまくいくと市松模様のタイル張りができあがります．

（問）Ｐがどのような形のとき，このようなタイル張り（平面の市松模様三角形タイル張り）が可能であろうか？

（答）これが可能なためには，１つの頂点で偶数個の３角形が交わらなければならないので，これを２ａとおく．また，その頂点の角度をαとおくと，頂点を一回りしたので，２ａα＝２π．ゆえに，

　　α＝π／ａ　　　ただし，ａは２以上の自然数．

　まったく，同様に残り２つの内角に対しても

　　β＝π／ｂ，γ＝π／ｃ

　また，α＋β＋γ＝πより

　　１／ａ＋１／ｂ＋１／ｃ＝１

　この等式を満たす（ａ，ｂ，ｃ）の組は非常に少ない．便宜上，ａ≧ｂ≧ｃとすると

　　（３，３，３）　→　正三角形

　　（４，４，２）　→　直角二等辺三角形

　　（６，３，２）　→　３０°，６０°，９０°の三角形

の３種類が得られる．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

　以上の解は平面を鏡映三角形で埋めることをユークリッド面（放物的）で考えたものですが，リーマン面（楕円的），ロバチェフスキー面（双曲的）を問題にするならば，解は非常に異なるものになります．

　　α＋β＋γ＞π，＝π，＜π

　すなわち

　　１／ａ＋１／ｂ＋１／ｃ＞１，＝１，＜１

に応じて楕円幾何学，ユークリッド幾何学，双曲幾何学の三角形が得られます．

　１／ａ＋１／ｂ＋１／ｃ＞１を満たす正の整数の組みたす（ａ，ｂ，ｃ）は高々有限個で，（ｎ，２，２）は正２面体群，（３，３，２）は正４面体群，（４，３，２）が正８（６）面体群，（５，３，２）は正２０（１２）面体群に対応しています．一方，１／ａ＋１／ｂ＋１／ｃ＜１の場合は（ｎ≧７，３，２），（ｎ≧５，４，２），（ｎ≧４，３，３），（ｎ≧３，４，３）など無限個あり，双曲幾何学における市松模様三角形タイル張りの可能性は無限にあることになります．

　すなわち，楕円的平面では基本領域は有限個しかなく，有限個の基本領域をならべることによって全平面を埋めつくすことができます．一方，双曲的平面の場合には，無限に多くの種類の基本領域があり，全平面を隙間なく埋めるには無限個必要となります．ユークリッド平面はその中間で，基本領域は有限種類しかないが，全平面を埋めつくすには無限個必要であるというわけです．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【４】モザイク模様とルート系

（問）１つの３角形を辺に関して次々折り返していって，３角形が互いに重なることなく，平面を埋めつくすことができるか？

（答）この問題も平面を鏡映三角形で埋めるというものですが，市松模様という条件がなくなっているので，１つの頂点に会する三角形は偶数に限る必要はありません．

　　α＝２π／ｐ　　　ただし，ｐは３以上の自然数．

　まったく，同様に残り２つの内角に対しても

　　β＝２π／ｑ，γ＝２π／ｒ

　また，α＋β＋γ＝πより

　　１／ｐ＋１／ｑ＋１／ｒ＝１／２

が成り立ちます．

　ここで，３≦ｐ≦ｑ≦ｒと仮定すると

　　１／２＝１／ｐ＋１／ｑ＋１／ｒ≦３／ｐ

より，３≦ｐ≦６

　さらに，ｐが奇数のとき，頂点Ａからでる２辺の長さは等しくならなければなりません．そうしないと，折り返しでうまく重ならないからです．したがって，

(i)ｐ＝３のとき，ｑ＝ｒなので，

　　ｑ（ｑ−１２）＝０

これより，（ｐ，ｑ，ｒ）＝（３，１２，１２）

(ii)ｐ＝４のとき，（ｑ−４）（ｒ−４）＝１６

これより，（ｐ，ｑ，ｒ）＝（４，５，２０），（４，６，１２），（４，８，８）ですが，（ｐ，ｑ，ｒ）＝（４，５，２０）は必要条件を満たすものの，十分条件を満たさない，すなわち，１点のまわりだけは完全に埋められても平面のタイル張りになりません．凸な多角形では七角以上になるとどんな型のものも平面充填はうまくいかないのです．

(iii)ｐ＝５のとき，ｑ＝ｒより，

　　ｑ（３ｑ−２０）＝０

これを満たす３以上の整数はありません．

(iv)ｐ＝６のとき，（ｑ−３）（ｒ−３）＝９

これより，（ｐ，ｑ，ｒ）＝（６，６，６）

　結局，求めるタイル張りは

　　（６，６，６）　→　正三角形

　　（４，８，８）　→　直角二等辺三角形

　　（４，６，１２）　→　３０°，６０°，９０°の三角形

　　（３，１２，１２）→　３０°，３０°，１２０°の三角形

の４通りあることになり，実際に十分条件を満たします．

　３０°，３０°，１２０°の角をもつ三角形は，正三角形格子（３，６）の各面を３個の合同な三角形に分解することによってできるモザイク模様です．「麻の葉」文様と呼ばれるくり返し文様なのですが，日本では古くから装飾工芸品や寄木細工のデザインなどとして用いられていますから，ご存じの方も多いと思います．

　３０°，６０°，９０°のモザイクは，３０°，３０°，１２０°の三角形からなるモザイクをさらに２個の直角三角形に分解してできる模様，直角二等辺三角形モザイクは正方格子（４，４）を４分割したもの，正三角形は正三角形格子（３，６）そのものです．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝