東京23区を「最も少ない色」で塗り分けるには何色必要か…解決まで124年もかかった数学の超難問を解説する
プレジデントオンライン / 2024年1月17日 15時15分
※本稿は、NHK「笑わない数学」制作班編『笑わない数学』(KADOKAWA)の一部を再編集したものです。
■「少ない数の色」で地図を塗り分ける方法
次の図は東京23区の地図です(図表1)。
これから、この地図を隣の区が同じ色にならないように塗り分けていきます。ただし、できるだけ少ない数の色で塗り分けます。
まずは、赤と青の2色で塗り分けられるかみてみましょう。
港区を赤、中央区を青で塗ると、両方の区に隣接する千代田区は赤でも青でも塗り分けることができません(図表2)。
![【図表2】2色で塗り分けられるか試した東京23区の地図](https://president.ismcdn.jp/mwimgs/4/2/1200wm/img_42dd50b3556a7376873b9a77adf681f8300987.jpg)
それでは、赤色と青色に黄色を加えた3色であればどうでしょうか? 千代田区を黄色で塗ることができます。
そして、新宿区は港区と千代田区に隣接するので青色、文京区は千代田区と新宿区に隣接するので赤色に塗り分けることができます。
すると、台東区は中央区、千代田区、文京区の3区に隣接するため、赤でも青でも黄でも塗り分けることができません(図表3)。
![【図表3】3色で塗り分けられるか試した東京23区の地図](https://president.ismcdn.jp/mwimgs/1/9/1200wm/img_19230d0108e5e3ac7d4dff0ee1540a13264789.jpg)
それでは、赤色、青色、黄色に緑色を加えた4色あればどうでしょうか? 台東区を緑色で塗ることができます。
さらにどんどん塗り分けていくと、4色あれば東京23区をすべて塗り分けることができました(図表4)。
![【図表4】4色で塗り分けた東京23区の地図](https://president.ismcdn.jp/mwimgs/6/4/1200wm/img_6421924d1493195cfd8332751eac39b3370710.jpg)
同じように、日本地図も4色で塗り分けられます(図表5)。
![【図表5】4色で塗り分けた日本地図](https://president.ismcdn.jp/mwimgs/e/6/1200wm/img_e664081bf80b05fb3a00b6e5d5dcdcae243338.jpg)
■世紀の難問「四色問題」とは
これまでの説明で「四色問題」がどのような問題か、おわかりいただけたのではないかと思います。
そうです。世の中のすべての地図は、4色あれば塗り分けられるのではないか、それをどうやったら証明できるのかが、世紀の難問「四色問題」なのです。
この問題は、1852年イギリスのロンドンで、ある若者が「どんな地図でも4色で塗り分けることができそうだ」と気がついたことから始まったと言われています。
その話を聞いたイギリスを代表する数学者の一人、オーガスタス・ド・モルガンは、このことを数学的に厳密に証明しようと思い立ちます。
しかし、ド・モルガンは証明に大苦戦。彼が学者仲間にこの難問をなげかけていったことで、四色問題は世に広まっていったのです。
ド・モルガン以外にも多くの数学者が四色問題に挑戦しましたが、誰も証明には到達できず、時間だけが流れていきました。
しかし、問題が生まれて27年後の1879年に四色問題を大きく前進させる論文が発表されました。
その論文の著者はアルフレッド・ケンプというロンドンで働く弁護士でした。
■「箱に入った地図を4色で塗り分けられるか」
ケンプはまず、ありとあらゆる地図を「国の数で地図を分類する」ことから始めました。それはつまり、下の図のように、1カ国の地図すべてが入った箱、2カ国の地図すべてが入った箱、……、100カ国の地図すべてが入った箱、……、10000カ国の地図すべてが入った箱、……とすべての地図を国の数で分類したのです(図表6)。
![【図表6】国の数で地図を分類した箱の絵](https://president.ismcdn.jp/mwimgs/2/0/1200wm/img_20fd217962312a890d663de2af58a0ed78987.jpg)
そして、それぞれの箱に入った地図が4色で塗り分けられるか考えたのです。
1カ国の地図たちは当然4色で塗り分けられますよね。1カ国しかない地図なのですから、4色のうちどれかの色で塗ってしまえば塗り分けられます。
つまり、1カ国の地図すべてが入った箱は4色で塗り分けOK。
同じように、2カ国の地図すべてが入った箱も、3カ国の地図すべてが入った箱も、4カ国の地図すべてが入った箱も4色で塗り分けOKということがわかります。
■難問解決のカギとなる仮定
では、この調子で5カ国すべてが入った箱、6カ国すべてが入った箱、……も4色で塗り分けOKと証明できるでしょうか? もしかしたら塗り分けOKと証明できるかもしれません。
ただ、何カ国の地図まで塗り分けられるかわからないので、とにかく1カ国の地図すべてが入った箱から、nカ国の地図すべてが入った箱までが4色で塗り分けOKになったと仮定したのです。
そして、ケンプはこんなことを言いました。
もし、ケンプの言っている“都合の良いこと”が本当にあるのなら、nカ国までの箱が全部OKだということから、n+1カ国の箱も自動的に全部OKということになります。
そして、さらに“都合が良いこと”によってn+2カ国の箱も自動的にOK、n+3カ国の箱もOK、……というように、まるでOKサインのバケツリレーのように、無限に続くすべての箱がOKだということがいえてしまいます。
![【図表7】nカ国に無限に国を足していく箱の絵](https://president.ismcdn.jp/mwimgs/a/a/1200wm/img_aa420bba60d8367fbe55ab764436c204436867.jpg)
つまり、この“都合が良いこと”が実際にあることが示せれば、四色問題は解決できるのです。
■「都合が良いこと」は本当に正しいのか
この先の目標は、この“都合が良いこと”が本当に正しいのかを確かめることです。
ケンプは次のことに着目します。
次のように、二カ国に接している国を「二辺国」、三カ国に接している国を「三辺国」、四カ国に接している国を「四辺国」、五カ国に接している国を「五辺国」と呼びます(図表8)。
![【図表8】二辺国から五辺国の地図](https://president.ismcdn.jp/mwimgs/5/e/1200wm/img_5efb4a7227a56ec99d65f7b9db5494b3321004.jpg)
ケンプが着目した事実を、まだ4色で塗り分けOKとわかっていないn+1カ国の箱に当てはめてみると、箱の中の地図たちは「二辺国」を含む地図、「三辺国」を含む地図、「四辺国」を含む地図、「五辺国」を含む地図の4つに分類できるのです。
![【図表9】二辺国から五辺国の4つに分けた箱の絵](https://president.ismcdn.jp/mwimgs/4/5/1200wm/img_45f1cf22b1b8db3cf3f435cf880d9f82325088.jpg)
ここからは、箱の中で4つに分類された地図がそれぞれ4色で塗り分けられるか考えていきます。
■ケンプの「天才的な発想」
まず、二辺国を含む地図について考えていきましょう。
ここで、ケンプは二辺国を消して考えてみるということを思いつきました(図表10)。
![【図表10】n+1カ国の地図から二辺国を1つ消してnカ国にした地図](https://president.ismcdn.jp/mwimgs/6/c/1200wm/img_6c42caf7c90239b31932c8027cfb4abf235467.jpg)
二辺国を消したこの地図の国の数は1カ国減りnカ国の地図になりました。nカ国の地図は、すべて4色で塗り分けできると仮定しているので、このnカ国の地図は4色で塗ることができます(図表11)。
![【図表11】4色で塗り分けたnカ国の地図](https://president.ismcdn.jp/mwimgs/5/1/1200wm/img_512f7c11d67f4e1b8d9e779e58813d81553336.jpg)
ここで、先ほど消してしまった二辺国を復活させます。
すると、二辺国は接している二カ国とは別の色で塗ることができますので、地図全体を4色で塗り分けられたということになります(図表12)。
![【図表12】二辺国を復活させて色分けした地図](https://president.ismcdn.jp/mwimgs/c/b/1200wm/img_cb15f9411d86941d6edc9cf5ad15f6e6401009.jpg)
つまり、二辺国をひとつでも含むn+1カ国の地図は、すべてこの方法で塗り分けOKだと証明できたことになります。
三辺国を含む地図、四辺国を含む地図も、同じように、1カ国減らして4色で塗り分けし、国を復活させて色を塗るという方法で塗り分けOKだと証明できます(図表13)。
(実は、四辺国を含む地図は単純にはいかないのですが、ケンプの天才的な発想で証明できます。)
![【図表13】色分けした四辺国を含む地図](https://president.ismcdn.jp/mwimgs/2/5/1200wm/img_25e9f0aba763f93ae616f970e216a863587080.jpg)
■最後の関門「五辺国」
四辺国を含む地図まで4色で塗り分けられることがわかったのですから、残るは五辺国をひとつでも含むn+1カ国の地図が4色で塗り分けられるかどうかです。
ケンプは1879年に発表した論文で、そのことを証明しましたが、その11年後に誤りであることが見つかります。
ケンプの方法では証明できないということがわかった後、多くの数学者たちが新しいアイデアを用いて証明に挑んだものの、長い間誰一人成功しませんでした。
しかし、20世紀にはいると、そんな絶望的な状況に僅かな希望を与える新たな証明方法が考案されます。
その方法とは、五辺国を含む地図をさらに細かく分類して、塗り分けられるか調べてみようというものです。
実は、五辺国を含む地図は、さらに次のように2つに分類できるのです(図表14)。
![【図表14】2つに分類した五辺国を含む地図](https://president.ismcdn.jp/mwimgs/b/a/1200wm/img_ba9c0b3666a0214942bd73a727024fe6101166.jpg)
分類した2つをそれぞれ4色で塗り分けられることを証明できれば解決です。
しかし、この方法でも、誰も証明にたどり着くことはできませんでした。
数学者たちは、さらに分類を行い、それでも駄目ならさらに分類することを繰り返すことになりました。
この方法で、4色で塗り分けられる分類をいくつか見つけることができたのですが、爆発的に増えていく分類は段々と手に負えなくなっていきました。
![【図表15】爆発的に増えていく分類の絵](https://president.ismcdn.jp/mwimgs/f/e/1200wm/img_feb1869dc8af463c6beaf78246b9e1d8429041.jpg)
■エレファント(elephant)な証明による決着
この作業はいつ終わるのか? そもそも終わりはあるのか? こうして四色問題の証明は人間には到達できない無謀な挑戦だと恐れられるようになっていきました。
四色問題が生まれて1世紀以上が過ぎた1970年代に、アメリカの数学者ウォルフガング・ハーケンとケネス・アッペルが、コンピュータで膨大な証明作業に挑んだのです。
そして、コンピュータを用いた計算開始から4年後、遂にコンピュータが証明の完了を告げます。
実に124年の時を経て、四色問題は解決されました。
![NHK「笑わない数学」制作班編『笑わない数学』(KADOKAWA)](https://president.ismcdn.jp/mwimgs/e/3/1200wm/img_e36c58a9a8263eb530adfc2b81a28fdc198591.jpg)
しかし、この証明は批判を浴びてしまいます。
当時の数学者は、コンピュータによる証明に馴染みがなかったため懐疑的な声があがったのです。
さらに、ひたすら分類を行う証明スタイルは泥臭すぎて「美しくない」とも言われ、「エレガントな証明」(elegant proof)を期待していた人からは「エレファントな証明」(elephant proof)と言われてしまったのです。
今ではコンピュータを使う証明も立派な証明方法とされています。しかし一方で、人間が本来持つ知性の底力を見せつけるような「エレガントな証明」が期待されているのも、また事実なのです。
----------
----------
(NHK「笑わない数学」制作班)
外部リンク
この記事に関連するニュース
-
人間の脳は誰でも確実に若返らせることができる!医学博士が語る驚くべき脳の特徴
THE GOLD ONLINE(ゴールドオンライン) / 2024年8月15日 11時0分
-
最旬・ミュートメイクのやり方をLUNASOLに聞いた -新色「アイカラーレーションN」のスウォッチも紹介
マイナビニュース / 2024年8月10日 9時45分
-
算数・数学の自由研究作品コンクール「MATHコン2024」に日本数学検定協会が9度めの協賛 とくに優れた応募作品に「日本数学検定協会賞」を授与
@Press / 2024年8月8日 11時0分
-
急拡大するAIビジネス、高まる電力需要!ウラン投資を始める三つの理由
トウシル / 2024年7月25日 7時30分
-
子供たちの園庭は「ぜいたく品」になった…「雑居ビル保育園」を生み出した安易な"待機児童ゼロ政策"の代償
プレジデントオンライン / 2024年7月24日 9時15分
ランキング
-
1注文住宅を建てた人が「後悔したこと」とは? 不動産専門家が教える! 間取りの「失敗ポイント」
ananweb / 2024年8月17日 19時30分
-
2親戚付き合い、6割超が必要と答えるも…「好きではない」理由は 2位「親しくないから」、3位「話題に困る」
まいどなニュース / 2024年8月17日 18時20分
-
3気づいたときには老化で耳は遠くなっている…難聴の専門家が勧める「耳の寿命」を伸ばす最強の食材リスト
プレジデントオンライン / 2024年8月17日 10時15分
-
4ホンダが最初に作ったクルマは超高性能な軽トラだった?
マイナビニュース / 2024年8月17日 11時30分
-
5マツダ「アイコニックSP」市販化へ! リトラライト&ロータリーエンジン搭載「スポーツカー」は400万円前後であるべき? 価格にさまざまな意見も
くるまのニュース / 2024年8月17日 11時10分
記事ミッション中・・・
記事にリアクションする
![](/pc/img/mission/mission_close_icon.png)
記事ミッション中・・・
記事にリアクションする
![](/pc/img/mission/point-loading.png)
エラーが発生しました
ページを再読み込みして
ください
![](/pc/img/mission/mission_close_icon.png)