京大 2024 年文系第 2 問：彩色多項式と立方体の塗り分け問題

2024 年の京都大学・文系数学で出題された立方体の塗り分け問題。初等的な数え上げによる解法と、大学で学ぶ「彩色多項式」を使った解法の 2 通りを紹介する。

問題の確認

$n$ 個の異なる色を用意し、立方体の各面にいずれかの色を塗る。各面にどの色を塗るかは同様に確からしいとする。辺を共有するどの 2 つの面にも異なる色が塗られる確率を $p_{n}$ とするとき、 $p_{3}$ と $p_{4}$ を求めよ。

立方体の隣接構造

まず、立方体の 6 面の位置関係を整理しよう。

上面	面 1
下面	面 6
前面	面 2
後面	面 5
左面	面 4
右面	面 3

「辺を共有する＝隣接する」という関係を整理すると、次のことがわかる。

上面と下面

互いには隣接しない（対面の関係）。ただし、側面 4 つすべてと隣接する。

側面 4 つ（前・右・後・左）

環状に並んでおり、前↔右↔後↔左↔前と隣り合っている。

この構造を利用して、上面→側面 4 つ→下面の順に塗る方法を数えていく。

解法 1：初等的な数え上げ

高校数学の範囲で解く方法である。

(1) $p_{3}$ を求める

3 色を A, B, C とし、全事象は $3^{6} = 729$ 通りである。

上面を色 A に固定して数えよう。対称性から、最後に 3 倍すればよい。

側面の塗り方

側面 4 つはすべて上面（色 A）と隣接するため、使えるのは B と C の 2 色だけだ。前面から順に考える。

前面は B か C → 2 通り

右面は前面と異なる → 1 通り

後面は右面と異なる → 1 通り

左面は後面・前面の両方と異なる必要がある

ここで、2 色しかないため、前→右→後と交互に塗ると自動的に左面も条件を満たす。

パターン 1

前 = B → 右 = C → 後 = B → 左 = C

パターン 2

前 = C → 右 = B → 後 = C → 左 = B

したがって、側面の塗り方は 2 通りである。

下面の塗り方

下面は側面 4 つすべてと隣接する。側面で B と C が両方使われているため、下面に使えるのは A だけだ。よって 1 通り。

合計

上面を A に固定したとき： $2 \times 1 = 2$ 通り

上面の色の選び方が 3 通りあるから、条件を満たす塗り方は $3 \times 2 = 6$ 通り。

$p_{3} = \frac{6}{729} = \frac{2}{243}$

(2) $p_{4}$ を求める

4 色を A, B, C, D とし、全事象は $4^{6} = 4096$ 通りである。

同様に上面を色 A に固定して考える。

側面の塗り方を数える

側面には B, C, D の 3 色が使える。前面から順に数えよう。

前面は B, C, D のどれか → 3 通り

右面は前面と異なる → 2 通り

後面は右面と異なる → 2 通り

左面は後面・前面の両方と異なる必要がある

左面の選択肢は「後面と前面が同色か異色か」で変わる。

後面と前面が同色の場合

左面は後面（＝前面）と異なればよい → 2 通り

後面と前面が異色の場合

左面は後面とも前面とも異なる → 1 通り

それぞれの場合の数を求めよう。

後面＝前面となる場合：

前面を決める（3 通り）→ 右面は前面と異なる（2 通り）→ 後面は前面と同じ（1 通り）→ 左面は後面と異なる（2 通り）

$3 \times 2 \times 1 \times 2 = 12$ 通り

後面≠前面となる場合：

前面を決める（3 通り）→ 右面は前面と異なる（2 通り）→ 後面は右面とも前面とも異なる（1 通り）→ 左面は後面とも前面とも異なる（1 通り）

$3 \times 2 \times 1 \times 1 = 6$ 通り

側面の塗り方は合計 $12 + 6 = 18$ 通りである。

下面の塗り方

下面は側面 4 つすべてと隣接するため、側面で使われていない色しか選べない。側面で何色使われたかで場合分けする。

側面が 2 色だけのとき：

前面＝後面、かつ右面＝左面となるパターンだ。前面の選び方が 3 通り、右面の選び方が 2 通りで、 $3 \times 2 = 6$ 通り。

このとき下面には、A と「側面で使われなかった 1 色」の 2 色が使える → 2 通り

側面が 3 色すべて使われるとき：

$18 - 6 = 12$ 通り。下面に使えるのは A だけ → 1 通り

合計

上面を A に固定したとき： $6 \times 2 + 12 \times 1 = 24$ 通り

上面の色の選び方が 4 通りあるから、条件を満たす塗り方は $4 \times 24 = 96$ 通り。

$p_{4} = \frac{96}{4096} = \frac{3}{128}$

解法 2：彩色多項式を使う

ここからは大学で学ぶ内容である。受験では使えないが、「彩色多項式」という強力な道具を紹介しよう。

彩色多項式とは

グラフ理論では、頂点の集まりと、それらを結ぶ辺の集まりをまとめて「グラフ」と呼ぶ。グラフの各頂点に色を塗り、辺で結ばれた頂点同士が異なる色になるようにする問題を「グラフ彩色」という。

$k$ 色でグラフを塗り分ける方法の総数を $P (k)$ と書くと、これは $k$ の多項式になることが知られている。これを彩色多項式という。

特に、 $n$ 個の頂点が環状につながったグラフ（サイクル $C_{n}$ ）の彩色多項式は次の公式で与えられる。

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

公式の導出

サイクル $C_{n}$ の彩色多項式を導出しよう。頂点を $v_{1}, v_{2}, \dots, v_{n}$ とし、 $v_{1} - v_{2} - \dots - v_{n} - v_{1}$ と環状につながっているとする。

$v_{1}$ と $v_{n}$ が同色かどうかで場合分けする。

$v_{1}$ と $v_{n}$ が異色の場合：

辺 $v_{n} - v_{1}$ を取り除いても塗り分け条件は同じだ。これは直線状のパス $P_{n}$ の彩色と同じで、

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

通りある。ただしこの中には「 $v_{1}$ と $v_{n}$ が同色」のパターンも含まれる。

$v_{1}$ と $v_{n}$ が同色の場合：

$v_{1}$ と $v_{n}$ を 1 つの頂点に縮約すると、サイクル $C_{n - 1}$ の彩色問題になる。よって $P_{C_{n - 1}} (k)$ 通り。

したがって、「 $v_{1}$ と $v_{n}$ が異色」のパターン数は

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

これがサイクル $C_{n}$ の彩色数そのものだから、漸化式

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

を得る。 $P_{C_{3}} (k) = k (k - 1) (k - 2)$ を初期条件として解くと

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

を得る。

問題への適用

立方体の側面 4 つは、前↔右↔後↔左↔前と環状につながっている。これはサイクル $C_{4}$ の構造だ。

(1) $p_{3}$ の計算

上面を色 A に固定すると、側面は B, C の 2 色で $C_{4}$ を塗る問題になる。

$P_{C_{4}} (2) = (2 - 1)^{4} + (2 - 1) = 1 + 1 = 2$

下面は側面 4 つすべてと隣接し、B と C が両方使われているので A しか選べない（1 通り）。

条件を満たす塗り方は $3 \times 2 \times 1 = 6$ 通りで

$p_{3} = \frac{6}{729} = \frac{2}{243}$

(2) $p_{4}$ の計算

上面を色 A に固定すると、側面は B, C, D の 3 色で $C_{4}$ を塗る問題になる。

$P_{C_{4}} (3) = (3 - 1)^{4} + (3 - 1) = 16 + 2 = 18$

下面の塗り方は、側面で使われた色の数による。

側面が 2 色のとき： 3 色から 2 色を選ぶのが $(2 3) = 3$ 通り、2 色で $C_{4}$ を塗るのが $P_{C_{4}} (2) = 2$ 通りで、計 6 通り。下面は 2 色使える。

側面が 3 色のとき： $18 - 6 = 12$ 通り。下面は A のみ。

上面固定時の塗り方は $6 \times 2 + 12 \times 1 = 24$ 通り。

条件を満たす塗り方は $4 \times 24 = 96$ 通りで