問題
下図は東北6県の地図です。この地図を見ながら、A社の営業部員3人が、それぞれの担当地域を決めようとしています。
隣り合う県を同じ人が担当しないようにしたい3人は、それぞれ別の色の色鉛筆で、自分の担当地域を塗りつぶしていくことにしました。3色の色えんぴつで下図を塗り分けるとすると、何通りの塗り方があるでしょう? ただし3色はあらかじめ指定されているとします。
(↓解答はずっと下にあります)
解答 6通り
上のほうから考えると、青森県に何色を塗るかは自由なので3通りあります。そのとき、残る2色を岩手県と秋田県のどちらに塗るかで2通りあり、合計6通りになります。
ところが、岩手県と秋田県の色が決まれば、宮城県の色が自動的に決まり、秋田県と宮城県の色が決まれば山形県の色が自動的に決まり、宮城県と山形県の色が決まれば福島県の色が自動的に決まるので、色分けは6通りで終わりです。
ところで、関西近辺の地図の場合、隣り合う府県を同じ色にならないように塗り分けるには3色では足りません。しかし「4色あれば、いかなる白地図でも塗り分けられる」ことがわかっています。これが証明困難で知られた4色問題です。