じぶん更新日記

じぶん更新日記・隠居の日々 1997年5月6日開設
Copyright(C)長谷川芳典

08月のインデックスへ戻る

最新版へ戻る

※クリックで全体表示。

　こちらに紹介されていた『ド・ラ・ヴァレ・プーサンの反例』(1896年)。ケンプ鎖の方法で4色に塗り替えることができない最小反例とのことであるが、単に4色に塗り分けるだけであれば画像のように簡単にできる。
　プーサンの業績についてはこちらに解説あり。複素解析の方法を使用して素数定理を証明したことなどで知られている。

2023年8月8日（火）
【連載】笑わない数学(7)四色問題(7)高齢者でもわかる『最小反例』　昨日の日記で、最小反例の、二辺国、三辺国、四辺国、五辺国について、「もし、○辺国を含む地図で最小反例があったとすれば、どういう矛盾が起きるのかを順に指摘していくというロジックについて述べた。例えば二辺国の場合は以下の通りとなる。Ａ国、Ｂ国と国境を接する二辺国（Ｃ国）を含む最小反例があると仮定する。その二辺国からＡ国との国境を1本消す（Ｃ国は隣のＡ国に吸収される）。Ａ国とＢ国は2色で塗り分けられる。Ａ国とＢ国の間にＣ国を復活させる。復活したＣ国は、3色目で塗り分けられるが、これは元の地図が最小反例であるという仮定に矛盾する。よって、最小反例は二辺国を含まないことが証明された。　しかし、このロジックは当初、高齢化により頭の回転が鈍くなった私にはよく分からないところがあった。すなわち、 ●5色を使わないと塗り分けられない地図があったと仮定しているので、この地図のどこかには依然として5色が必要は領域が残っているはずだ。なのにどうしてその領域には言及せず、二辺国だけに目を向けているのか？という疑問である。ネットで検索してみたが、この疑問について解説しているサイトは見つからなかった。数学がよく分かっている人たちにとってはあまりにも当たり前であり、そもそも疑問自体が生まれないということかもしれない。　その後、私自身もある日とつぜん「あっ、そういうことだったのか！」と、最小反例のロジックに気づくことができた。そこで、以下に、「高齢者でもわかる『最小反例』」というタイトルで、その内容を記すことにしたい。なお「高齢者でもわかる」というのは単に「高齢者の私でもわかる」という意味であり、「中学生にもわかる」としても趣旨は変わらない。「サルでもわかる」でもよいのだが、さすがにサルでは分からないと思う。　まず、この背理法の仮定は、 ●5色なければ塗り分けられない（平面）地図が存在すると仮定することにある。しかし、国の数が全部で3つとか4つとかの地図は必ず4色で塗り分けられる。なので、上記の仮定は、【仮定1】nカ国の地図の中には4色では絶対に塗り分けられない地図が存在するという仮定に置き換えることができる。このnの最小値が存在すれば最小反例になり、またnが存在しなければ仮定は間違っていたことになる。ちなみにこの【仮定1】は、次の【仮定2】と両立しなければならない。【仮定2】n-1カ国の地図は必ず4色で塗り分けられるなぜならば、もしn-1カ国でも絶対に5色が必要という地図があったとすると、nが最小値であるという仮定に反するからである。　以上をふまえたうえで、二辺国、三辺国、四辺国、五辺国の順に検討していくことになる。ここでなぜ六辺国以上は検討しなくても良いのかと言えば、六辺国以上が含まれている地図であっても、オイラーの多面体定理によりそのどこかには五辺国以下の国が少なくとも1つ含まれているからである。例えば蜂の巣のようにすべての国が六角形の形で隣接している地図はすべてが六辺国であるように思われるがこれは無限に広がっている場合の話。その世界の果てにある国は三辺国または四辺国になっていることが分かる。　なお、放送では、あらゆる地図を二辺国、三辺国、四辺国、五辺国という4つの箱に分類していたが、中には二辺国と三辺国の両方を含む地図もあるのでこれは正確ではない。正しくは、二辺国を含む地図二辺国は存在しないが三辺国を含む地図二辺国と三辺国は存在しないが四辺国を含む地図二辺国と三辺国と四辺国は存在しないが五辺国を含む地図というように分類して1.から順に検討することになる。　さて上掲の二辺国の場合の検討であるが、もう一度、そのプロセスを再掲すると以下のようになる。Ａ国、Ｂ国と国境を接する二辺国（Ｃ国）を含む最小反例があると仮定する。その二辺国からＡ国との国境を1本消す（Ｃ国は隣のＡ国に吸収される）。Ａ国とＢ国は2色で塗り分けられる。Ａ国とＢ国の間にＣ国を復活させる。復活したＣ国は、3色目で塗り分けられるが、これは元の地図が最小反例であるという仮定に矛盾する。よって、最小反例は二辺国を含まないことが証明された。ここから次のようなことが言える。上掲の1.は、そのような地図がnカ国から構成されていることを仮定している。すなわち地図のどこかにはどうしても5色が必要となるエリアが存在しているという仮定である。この仮定は実は間違っているのだが、仮定と言っている以上はそれを前提とすることが必要。次の2.の国境を消すという操作はnカ国だった地図がn-1カ国に減るということを意味している。そうすると、【仮定2】n-1カ国の地図は必ず4色で塗り分けられるという【仮定2】から、その地図は4色で塗り分けられなければならない。ここで注意したいのはＣ国を消滅させたことで自動的に地図の塗り分けが4色に減るという意味ではないという点。そうではなくて、Ｃ国を消滅させた後で何らかの塗り替えを行えば、4色だけで塗り分けができるようになるということを言っているのである。この場合、わざわざ塗り替えの方法をみつける必要は全くない。nが最小であると仮定している以上、それよりも1つ小さいn-1は必ず塗り分けられるはずだからだ。でもって、再びＣ国を復活させる。しかしＣ国の色はＡ国、Ｂ国以外の色で塗ればよいので、5色目を追加する必要なない。ところが、Ｃ国を追加した地図は、最初にあったnカ国の地図と同一である。同一である以上は、塗り分けに必要な色も同じ数になるはずなのに、最初の仮定では「5色が絶対必要」と言っておいて、後では「4色で塗れる」となるのでこれは矛盾、ということで最初の仮定は間違っており、最小反例となるnは存在しないことが証明された。ということになる。　同じ方法は三辺国でも使える。なぜなら、例えば、Ａ、Ｂ、Ｃという3国に囲まれたＤ国を消滅させたあとで復活させた場合、Ｄ国は周りを3色で囲まれていることから4色目で塗れば塗り分けが完成できるからである。　いっぽう四辺国となるとそうはいかない。そこで登場するのが『ケンプ鎖』ということになる。　次回に続く。