領域の塗り分け(隣接する領域)

方針

解答

⓪ 発想 — どう考え始めるか。 塗り分けは、制約のいちばんきつい領域から決めるのが定石だ。

全部の扇形と接している中心を、最初に塗る。すると残りは、輪に並んだ扇形どうしの隣接だけの問題になる。

輪の塗り分けは、最後の $1$ 枚が最初の $1$ 枚とも隣り合う。そこで衝突が起こりうると、先に見抜いておく。場合分け、または数え直しが要る合図だ。

中心を決める: 中心の色は4通り、どれでもよい。

扇形を決める: 4つの扇形を輪の順に $S_1,S_2,S_3,S_4$ とする($S_1$-$S_2$-$S_3$-$S_4$-$S_1$ がとなり合う)。各扇形は中心と違う色でなければならないので、使えるのは中心以外の3色だ。この3色で、輪をなす4つの扇形を、となりどうし違うように塗る。

$S_1$ は3通り。$S_2$ は $S_1$ と違う2通り。$S_3$ は $S_2$ と違う2通り。問題は $S_4$ で、$S_3$ とも $S_1$ とも違う色でなければならない。$S_1$ と $S_3$ が同じ色か違う色かで $S_4$ の選択肢が変わるので、単純なかけ算だけでは処理できない。

こういう『輪(サイクル)の塗り分け』は、次の公式で数えられる。$n$ 個の領域が輪をなすとき、$k$ 色でとなりどうし違うように塗る方法は

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

通りだ。いま扇形は $n=4$ 個、使える色は中心以外の $k=3$ 色だから

$$(3-1{)}^4+(-1{)}^4(3-1)=2^4+2=16+2=18(\text{通り})$$

かけ合わせる: 中心の4通りと扇形の18通りは別々に選べるので

$$4\times 18=72(\text{通り})$$

まとめ:もし扇形が輪ではなく一列(両はしがつながらない)なら $3\times 2\times 2\times 2=24$ 通りで済む。でも輪では、両はし(最初と最後)もとなり合うぶん条件が増える。図の形が『輪か一列か』を正しく読み取るのが、塗り分けの出発点だ。

発展 — 一歩先へ。 この図は、中心の点を $4$ つの扇形すべてとつなぎ、扇形どうしを輪でつないだ形だ。グラフ理論では車輪グラフ $W_4$ と呼ばれる。

「隣り合う領域は違う色」という塗り分けの数は、色数 $k$ を変数と見ると $k$ の多項式になる。これを彩色多項式という。$W_4$ の彩色多項式に $k=4$ を代入すると、ちょうど $72$ が出る。

地図の塗り分け(四色定理)も、この彩色多項式の枠組みで語られる。図形の隣接関係をグラフに直すと、塗り分けが代数の問題に変わる。

別解

別解 — 輪の公式を使わず場合分けで数える(苦手な人向けの手作業ルート)。 扇形に使えるのは中心以外の $3$ 色。この $3$ 色で輪 $S_1$-$S_2$-$S_3$-$S_4$-$S_1$ を塗る数を、じかに数える。

$S_1$ は $3$ 通り。$S_2$ は $S_1$ と違う $2$ 通り。ここまでは素直だ。

問題の $S_4$ は $S_3$ とも $S_1$ とも違わねばならない。そこで $S_3$ の色で場合を分ける。$S_3$ は $S_2$ と違えばよいので、候補は $S_1$ と「残りの $1$ 色」の $2$ つ。

• $S_3=S_1$ のとき:$S_4$ は $S_3=S_1$ を避ければよく、$3$ 色から $1$ 色を除いて $2$ 通り。
• $S_3$ が残りの $1$ 色のとき:$S_4$ は $S_3$ とも $S_1$ とも違い、この $2$ 色は別なので $1$ 通り。

$S_3,S_4$ の決め方は $1\cdot 2+1\cdot 1=3$ 通り。よって扇形は $3\cdot 2\cdot 3=18$ 通り。中心 $4$ 通りとかけて

$$4\times 18=72.$$

公式を覚えていなくても、最後の $1$ 枚の衝突を場合分けで押さえれば、同じ $72$ 通りにたどり着く。