四色定理の驚くほど簡単な証明

以前のブログで説明がなかなか納得されない例として四色定理を取り上げましたが、実際にどこが納得しがたいのか知りたいと思い勉強してみることにしました。とはいえ、原論文をいきなり読むのはハードルが高すぎるので “Four Colors Suffice: How the Map Problem Was Solved” を読むことから始めました。(この本はカラーの図版も美しく、四色定理をめぐる歴史も丁寧に説明しているので大変おすすめです。”四色問題”というタイトルで翻訳も出ているようです。)

完全に理解できているわけではありませんが、物議を醸した最初の証明(ちなみにココココで論文が無料で見れます)は次の2段階から構成されていたようです。

  1. 平面上の地図が必ず一つは含むパターンを列挙する
  2. 地図からそのパターンを取り除いてできる地図が4色で塗れるならば、元の地図も4色で塗れることを示す

第一段階目で見つけたパターンがこの論文の最後に並べ立てられていますが、76ページの論文のうち62 ページを占めています。これは素人目にも数学の証明というより力押しと感じる量です。しかも著者自身が、実際にはこれよりも少ない数でも足りるかもしれない、つまり、このリストについて第二段階を実行すれば四色定理は証明できるけれども、もっと短いリストを使ってもできるかもしれない、と明言しています。(実際、もっとも短いリストが後年別の研究者により発表されています。)さらに第二段階はいくつかのヒューリスティクスの組合せをコンピュータに虱潰しに実行させることで証明しています。

驚くべき証明

流石にこれは「なんだかなぁ」という感じるのは素人だけではなく、本職の数学者も同じようです。たまたまこんな論文を見つけました。

Hemanta K. Baruah “A NON-ALGORITHMIC PROOF OF THE FOUR COLOR CONJECTURE

概要の “We claim that this is the proper mathematical proof of the four color conjecture, for which the world of mathematics had been waiting for nearly one hundred and sixty years.” という文からも、著者の「こういうのを証明って言うんだ!」という意気込みが感じられます。

驚くべきことにこの論文はたった8ページで、しかもその証明を理解するのにはなんら高度な数学の知識は必要ありません。簡単にここに紹介したいと思います。

  1. 5つの国だけからなる地図は4色で塗りわけることができる。
  2. 地図の外周(実際の地図で言うと海に面している部分)にある国は3色で塗りわけることができる。
  3. いま国の数が n の地図は4色で塗り分けられると仮定し、その外周に国を一つ追加し、n+1 個の国からなる地図を作ることを考える。2. より元の地図の外周で使われていない色があるはずである。その色で追加した国を塗れば、n+1個の国全体が4色で塗り分けられる。
  4. 1. の5つの国からスタートして 3. の手順を繰り返せば任意の大きさの地図を4色で塗りつぶすことができる。(証明終わり)

なんというシンプルさ!こんな簡単な証明がつい最近まで気づかれずにいたというのはまったく驚きです。

落とし穴はどこにある?

… というような話では残念ながらなく、この「証明」には間違いがあります。1. と 2.  は正しそうです。4. は単に帰納法を適用しただけなのでそこに間違いがあるとも考えにくいです。さて、どこに落とし穴があるのでしょうか?(ちなみ四色定理が成立するので、反例をあげて反証するという手は使えません。証明の論理に穴があります。)

四色定理の驚くほど簡単な証明” への5件のフィードバック

  1. 「任意の大きさの地図を4色で塗りつぶすことができる。」
    からといって
    「任意の地図を4色で塗り分けられる」
    とは限らない。ですかね?

    いいね

    1. どんな地図でも外側から一つずつ国を取り除いていけば、いずれ国の数は5つまで減ります。(4カ国以下の地図が4色で塗り分けられるのは自明なので除外してます。)取り除いたのと逆の順番に国を足していけば元の地図が復元できるので、3の手順で元の地図まで辿り着くことができます。

      いいね

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト /  変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト /  変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト /  変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト /  変更 )

%s と連携中