四色問題とは何か?四色定理の歴史と塗り絵パズルのコツ

最近、スマホの「塗り絵パズル」にハマっています。

いや~、コレ、本当に面白いですよ。

つい、時間を忘れて遊んでしまいます。

それで、この塗り絵パズルなんですが、

「四色問題(四色定理)」

という有名な定理を利用したものなんですね。

今回は、この四色問題についてのお話です。

スポンサーリンク
レクタングル(大)広告

■ 四色問題(四色定理)について

▼ 四色問題(四色定理)とは?

四色問題を一言で説明すると、

どんなに複雑な塗り絵でも、
色が4色あれば、
隣り合う面が同じ色にならないように塗り分けられる。

というものなんです。

たとえば、下のような塗り絵があったとしますよね。

ポインセチア塗り絵

これを4色を使って塗り分けると、

ポインセチア塗り絵完成

こーんなに美しい作品に仕上がるわけです。

ちなみに、以下は私が作った問題。

塗り絵2

すべての面が他の5つの面と接している図です。

シンプルですが、意外と難しいですよ。

解答例はこちら。

塗り絵2完成

うまく塗り分けることはできましたか?

▼ 塗り絵パズルのコツ

それで、この「塗り絵パズル」の解き方なんですが、

以下のことを意識して塗っていくと成功しやすいです。

1. 多くの面と接している面から塗っていく。
2. 飛ばし塗りをせずに、塗った所から順番に塗っていく。
3. 塗れる色の数が少ない所から塗っていく。
たとえば、ある面の周りがすでに3色で囲まれてしまっている場合、
その面は残り1色でしか塗れないわけですから、優先的に塗るということです。
4. 周りが4色に囲まれてしまっても諦めない。
周りの色がさらにその周りの色と交換できないか検討します。
交換できれば、囲まれている色数を4色から3色に減らすことができます。

スポンサーリンク

▼ 四色問題の歴史について

ここで、四色問題の歴史について、ミニドラマで再現したいと思います。

~ 登場人物 ~

フレデリック・ガスリー … イギリスの学生。後に物理学者になる。

ド・モルガン … イギリスの数学者。「ド・モルガンの法則」はあまりにも有名。

ウィリアム・ローワン・ハミルトン … イギリスの著名な数学者。

~ ストーリー ~

時は19世紀のイギリス。

ある大学で、こんな会話が交わされました。

ガスリー: 先生! 「地図上で隣り合う国を異なる色で塗っていくとき、4色あれば十分か?」と兄に聞かれたのですが、先生はどう思われますか?

ド・モルガン: ふむ、ふむ。それはだね…。

~ ここから心の声 ~

…何だ、この意味不明な質問は。

一見簡単そうだが、考えても全然分からんぞ。

しかし、私はド・モルガンだ。

大学教授ともあろう者が、学生の手前、まさか「分からない」なんて言えないし…。

あぁ、困った、どうしよう、どうしよう。

とりあえず、この場は何とかしのごう。

~ 心の声終わり ~

ド・モルガン: ふむ。いい質問だ。実に興味深い問題だから、私の方でも調べておこう。おととい来なさい。

ガスリー: 先生、それって「二度と来るな」って意味ですよ。

ド・モルガン: いいから、行きなさい! 勉強しなさい!

そして、ド・モルガンはイギリスの著名な数学者であるハミルトンに手紙を書きます。

~ ハミルトンへの手紙 ~

ド・モルガン: まだ起きてるにゃん?

ハミルトン: 今から寝るとこ

ド・モルガン: ちょっとだけ話を聞いてほしいにゃん?

ハミルトン: どうした?

ド・モルガン: 学生が「地図は4色で塗り分けられるか」とか聞いてきて、泣きそうにゃん。(ノД`)・゜・。

ハミルトン: 頑張れww

これが、四色問題の始まりと言われています。

その後、「ケネス・アッペル」「ヴォルフガング・ハーケン」によってこの四色問題は証明されたことになっているんですが、

どうもその手法というのがコンピューターを用いた力技のようで、

ありとあらゆるパターンの地図を用意し、

「全パターンがコンピューターで4色に塗り分けられたから、この定理は正しい」

という証明の仕方のようなのです。

「俺は、そんなものを証明とは認めない!」

膨大な数の直角三角形を用意して、

コンピューターで、「底辺2乗+高さ2乗=斜辺2乗」が成り立つか調べて、

「全部成り立つから三平方の定理は正しい」

とか言っているようなものですよ。

「何じゃ、そりゃ」と。

証明とは、誰が読んでも納得できて、

シンプルでエレガントなものでなければいけないと思うんです。

であるならば、この四色問題を僕がエレガントに証明してやろうと。

次回からは、四色問題の証明に必要となる知識の話になります。

次の記事 → グラフ理論の双対グラフ、平面グラフと平面的グラフ、オイラーの定理

スポンサーリンク
レクタングル(大)広告
レクタングル(大)広告

シェアする

  • このエントリーをはてなブックマークに追加

フォローする