隣り合う領域は違う色にする｜地図と円グラフの塗り分け

横に並んだ 4 つの領域を 3 色で塗り分けると 24 通り。同じ 4 領域でも、円形に並んでいれば 18 通りになります。

差は両端が接するかどうかだけ。塗り分けの問題は、どの領域とどの領域が隣り合うかを先に書き出せば片づきます。

塗る順を決めて 1 つずつ

塗り分けは、領域を 1 つずつ塗っていく作業です。塗るたびに、すでに塗った隣の色が選べなくなる。

隣り合う領域を違う色にすることを、正しい塗り分けといいます^[1]。

塗る順を工夫すると、段ごとの選択肢の数がそろいます。そろえば掛け算で済む。

一列に並ぶ場合

領域が横一列に $n$ 個並び、隣どうしだけが接しているとします。$k$ 色で塗る。

左端は $k$ 通り。以降は直前と違えばよいので $k-1$ 通りずつです。

$$k(k-1{)}^{n-1}$$

3 色で 4 領域なら $3\times 2^3=24$ 通り。4 色で 5 領域なら $4\times 3^4=324$ 通り^[1]。

輪になると両端が接する

同じ 4 領域でも、円グラフのように輪になっていると、いちばん端どうしも隣り合います。

一列の値から、両端が同じ色になっている場合を引きます。両端が同じ色なら、その 2 つをまとめて $n-1$ 個の輪と見られる。

$n$ 個の輪の通り数を $C_n$ とすると、次の関係になります。

$$C_n=k(k-1{)}^{n-1}-C_{n-1}$$

3 色なら、三角形の $C_3=3\times 2\times 1=6$ から順に $C_4=24-6=18$、$C_5=48-18=30$、$C_6=96-30=66$。

閉じた式もあります^[1]。

$$C_n=(k-1{)}^n+(-1{)}^n(k-1)$$

$k=3$、$n=4$ なら $2^4+2=18$ で合いました。

中心がある形

円を中心の 1 つと、そのまわりの扇形に分ける形もよく出ます。中心はすべての扇形と接しています。

中心を先に塗ります。$k$ 通り。残る扇形は、中心と違う色でなければならないので $k-1$ 色しか使えません。

外側の扇形どうしは輪になっているので、$k-1$ 色での輪の塗り分けになる。

$$k\times \{(k-2{)}^n+(-1{)}^n(k-2)\}$$

例：中心と 3 つの扇形

4 色で、中心 1 つと外側 3 つを塗り分けます。

中心が 4 通り。外側の 3 つは互いに隣り合っていて、中心とも違う色でなければならない。残る 3 色を 3 つの扇形に並べる形です。

$3!=6$ 通りなので、$4\times 6=24$ 通り。

式でも確かめます。$4\times \{2^3-2\}=4\times 6=24$ で一致しました。

例：中心と 4 つの扇形

同じく 4 色で、外側が 4 つの場合。

$4\times \{2^4+2\}=4\times 18=72$ 通りです。

3 色だと外側に使えるのが 2 色だけになります。$3\times \{1^4+1\}=3\times 2=6$ 通り。外側は 2 色を交互に置くしかない。

例：田の字

正方形を 4 つに分けた形です。上下と左右は接しますが、対角は角で触れているだけなので接しません。

角だけで触れている領域は、隣り合うとは数えません^[2]。だから 4 領域が輪になった形と同じになる。

3 色で 18 通り、4 色で 84 通りです。対角を隣り合うと誤ると、まったく違う答えになります。

例：色をすべて使う場合

「4 色すべてを使って塗り分ける」と指定されると、条件が 1 つ増えます。

一列 4 領域を 4 色すべてで塗るなら、4 領域に 4 色を 1 つずつ配ることになる。全部違う色なので、隣り合う条件は自動的に満たされます。

$4!=24$ 通りです。

一般には、使う色の数で場合分けして引き算します。4 色までで塗る 108 通りから、3 色以下で塗る場合を引く形になる。

3 色以下で塗るのは、色の選び方 ${}_4{\mathrm{C}}_3=4$ 通りに $3\times 2^3=24$ を掛けて 96。ただし 2 色以下を引きすぎているので足し戻します。

$$108-96+{}_4{\mathrm{C}}_2\times 2=108-96+12=24$$

24 通りで、直接数えた値と合いました。

例：地図の形をした問題

県や国の形で出される問題も、接している組を書き出せば同じになります。

まず接する組を一覧にする。次に、いちばん多くの領域と接しているところから塗る。

接する数が最大の領域を後回しにすると、そこだけ選択肢が場合によって変わり、掛け算が崩れます。

何色あれば足りるか

平面の地図は、どんな形でも 4 色あれば塗り分けられます。1976 年にアッペルとハーケンが計算機を使って証明しました^[2]。

ただし、角だけで接する領域を別の色にする必要はない、という約束のもとでの話です。この約束がないと、必要な色数はいくらでも増えます。

高校の問題で「何色必要か」を問われるのは、ごく小さい図に限られます。実際に塗ってみるのが速い。

例：三角形を 4 つに分ける

大きい三角形を、中点を結んで 4 つの小三角形に分けます。真ん中の 1 つが、外側の 3 つすべてと接する形。

中心と 3 つの扇形の場合とまったく同じ構造です。4 色なら 24 通り、3 色なら $3\times \{1^3-1\}=0$ 通り。

3 色では塗り分けられません。真ん中と外側 3 つで、互いに接する 4 領域ができているためです。

よくある誤り

隣り合う組を書き出して、輪があるかどうかを見る。この 2 つで、使う式が決まります。

参考文献

^[1] が正しい塗り分けと一列や輪の個数、^[2] が 4 色定理と隣接の約束、^[3] が塗り分けの個数を多項式で表す考え方、^[4] と ^[5] が各国語での基本の数え方です。