最近、スマホの「塗り絵パズル」にハマっています。
いや～、コレ、本当に面白いですよ。
つい、時間を忘れて遊んでしまいます。
それで、この塗り絵パズルなんですが、
「四色問題（四色定理）」
という有名な定理を利用したものなんですね。
今回は、この四色問題についてのお話です。
■ 四色問題（四色定理）について
▼ 四色問題（四色定理）とは？
四色問題を一言で説明すると、
色が4色あれば、
隣り合う面が同じ色にならないように塗り分けられる。
というものなんです。
たとえば、下のような塗り絵があったとしますよね。
これを4色を使って塗り分けると、
こーんなに美しい作品に仕上がるわけです。
ちなみに、以下は私が作った問題。
すべての面が他の5つの面と接している図です。
シンプルですが、意外と難しいですよ。
解答例はこちら。
うまく塗り分けることはできましたか？
▼ 塗り絵パズルのコツ
それで、この「塗り絵パズル」の解き方なんですが、
以下のことを意識して塗っていくと成功しやすいです。
たとえば、ある面の周りがすでに3色で囲まれてしまっている場合、
その面は残り1色でしか塗れないわけですから、優先的に塗るということです。
周りの色がさらにその周りの色と交換できないか検討します。
交換できれば、囲まれている色数を4色から3色に減らすことができます。
・四色問題の解き方。塗り絵パズルアプリで行き詰まったときの対処法
▼ 四色問題の歴史について
ここで、四色問題の歴史について、ミニドラマで再現したいと思います。
～ 登場人物 ～
・フレデリック・ガスリー … イギリスの学生。後に物理学者になる。
・ド・モルガン … イギリスの数学者。「ド・モルガンの法則」はあまりにも有名。
・ウィリアム・ローワン・ハミルトン … イギリスの著名な数学者。
～ ストーリー ～
時は19世紀のイギリス。
ある大学で、こんな会話が交わされました。
ガスリー： 先生！ 「地図上で隣り合う国を異なる色で塗っていくとき、4色あれば十分か？」と兄に聞かれたのですが、先生はどう思われますか？
ド・モルガン： ふむ、ふむ。それはだね…。
～ ここから心の声 ～
…何だ、この意味不明な質問は。
一見簡単そうだが、考えても全然分からんぞ。
しかし、私はド・モルガンだ。
大学教授ともあろう者が、学生の手前、まさか「分からない」なんて言えないし…。
あぁ、困った、どうしよう、どうしよう。
とりあえず、この場は何とかしのごう。
～ 心の声終わり ～
ド・モルガン： ふむ。いい質問だ。実に興味深い問題だから、私の方でも調べておこう。おととい来なさい。
ガスリー： 先生、それって「二度と来るな」って意味ですよ。
ド・モルガン： いいから、行きなさい！ 勉強しなさい！
そして、ド・モルガンはイギリスの著名な数学者であるハミルトンに手紙を書きます。
～ ハミルトンへの手紙 ～
ド・モルガン： まだ起きてるにゃん？
ハミルトン： 今から寝るとこ
ド・モルガン： ちょっとだけ話を聞いてほしいにゃん？
ハミルトン： どうした？
ド・モルガン： 学生が「地図は4色で塗り分けられるか」とか聞いてきて、泣きそうにゃん。(ノД`)・゜・。
ハミルトン： 頑張れｗｗ
これが、四色問題の始まりと言われています。
その後、「ケネス・アッペル」と「ヴォルフガング・ハーケン」によってこの四色問題は証明されたことになっているんですが、
どうもその手法というのがコンピューターを用いた力技のようで、
ありとあらゆるパターンの地図を用意し、
「全パターンがコンピューターで4色に塗り分けられたから、この定理は正しい」
という証明の仕方のようなのです。
「俺は、そんなものを証明とは認めない！」
膨大な数の直角三角形を用意して、
コンピューターで、「底辺2乗＋高さ2乗＝斜辺2乗」が成り立つか調べて、
「全部成り立つから三平方の定理は正しい」
とか言っているようなものですよ。
「何じゃ、そりゃ」と。
証明とは、誰が読んでも納得できて、
シンプルでエレガントなものでなければいけないと思うんです。
であるならば、この四色問題を僕がエレガントに証明してやろうと。
次回からは、四色問題の証明に必要となる知識の話になります。