トップ› 京都大学› 1999年› 文系第5問

京都大学 1999年文系第5問解説

方針・初手

$n$ 角柱の面は、「上面」「底面」および $n$ 個の「側面」からなります。上面と底面はすべての側面と隣り合っているという立体特有の条件に注目します。側面に使える色の数は、上面と底面が「同じ色」か「異なる色」かによって変わるため、ここで場合分けを行います。側面の塗り分けは「環状に並んだ $n$ 個の面を $r$ 色で隣り合わないように塗る」という典型的な数え上げ問題に帰着されるため、漸化式を立てて処理します。

解法1

$n$ 角柱の $n+2$ 個の面を、上面、底面、および $n$ 個の側面と呼ぶ。各面には番号が書かれているため、回転して一致する塗り方も異なるものとして数える。上面と底面は互いに隣り合わないが、どちらも $n$ 個の側面のすべてと隣り合う。また、側面どうしは環状に並び、隣り合っている。

(1)

$P_2$ について：用意された色は $2$ 色である。上面にいずれか $1$ 色を塗ると、すべての側面は上面と隣り合うため、残りの $1$ 色でしか塗ることができない。しかし、$n \geqq 3$ であるから側面の面どうしは必ず隣り合い、これらをすべて同じ色で塗ると条件を満たさない。したがって、$P_2 = 0$ である。

$P_3$ について：用意された色は $3$ 色である。上面と底面の色の選び方で場合分けをする。

（i）上面と底面を異なる色で塗る場合上面と底面で $2$ 色を使うと、側面は上面とも底面とも異なる色にする必要があるため、残りの $1$ 色でしか塗れない。先ほどと同様に、側面を $1$ 色で塗ると隣り合う面が同色になるため不適である。よって $0$ 通り。

（ii）上面と底面を同じ色で塗る場合上面と底面の色を $1$ 色選ぶ方法は $3$ 通りである。このとき、側面で使える色は残り $2$ 色となる。$n$ 個の環状の面を $2$ 色で隣り合わないように塗るには、$2$ 色を交互に塗るしかない。したがって、$n$ が偶数のときは $2$ 通りであり、$n$ が奇数のときは最初と最後の面が同色になってしまうため $0$ 通りである。よって、この場合は $n$ が偶数なら $3 \times 2 = 6$ 通り、$n$ が奇数なら $0$ 通りとなる。

以上より、 $n$ が偶数のとき、$P_3 = 6$ $n$ が奇数のとき、$P_3 = 0$ である。

(2)

$n=7, k=4$ のときの $P_4$ を求める。一般に、$m$ 個の面が環状に並んでいるとき、$r$ 色を用いて隣り合わないように塗る方法の数を $a_m(r)$ とする（$m \geqq 3, r \geqq 2$）。一直線に並んだ $m$ 個の面を $r$ 色で塗る方法は、最初の面が $r$ 通り、それ以降は直前の面と異なる色を選ぶため $r-1$ 通りずつあり、総数は $r(r-1)^{m-1}$ 通りである。このうち、両端の面が異なる色であるものが求める $a_m(r)$ 通りである。一方、両端の面が同じ色であるものは、両端を同一視して $m-1$ 個の環状の面を塗る方法と等しいため、$a_{m-1}(r)$ 通りである。よって、以下の漸化式が成り立つ。

$$ a_m(r) + a_{m-1}(r) = r(r-1)^{m-1} $$

これを変形すると、

$$ a_m(r) - (r-1)^m = - \{ a_{m-1}(r) - (r-1)^{m-1} \} $$

となるから、数列 $\{a_m(r) - (r-1)^m\}$ は公比 $-1$ の等比数列である。 $m=3$ のとき、$3$ つの環状の面を $r$ 色で塗る方法は $a_3(r) = r(r-1)(r-2)$ 通りであるから、

$$ a_3(r) - (r-1)^3 = r(r-1)(r-2) - (r-1)^3 = (r-1) \{ r(r-2) - (r-1)^2 \} = (r-1)(-1) = -(r-1) $$

よって、一般項は以下のようになる。

$$ a_m(r) - (r-1)^m = -(r-1) \cdot (-1)^{m-3} = (-1)^m (r-1) $$

$$ a_m(r) = (r-1)^m + (-1)^m (r-1) $$

さて、$n=7, k=4$ の場合を考える。側面の数は $7$ 個である。

（i）上面と底面を同じ色で塗る場合上面と底面の色を選ぶ方法は $4$ 通りである。側面で使える色は残りの $3$ 色であるから、$r=3, m=7$ として $a_7(3)$ を計算する。

$$ a_7(3) = (3-1)^7 + (-1)^7 (3-1) = 2^7 - 2 = 128 - 2 = 126 $$

よって、この場合は $4 \times 126 = 504$ 通りである。

（ii）上面と底面を異なる色で塗る場合上面と底面の色を選ぶ方法は $4 \times 3 = 12$ 通りである。側面で使える色は残りの $2$ 色であるから、$r=2, m=7$ として $a_7(2)$ を計算する。

$$ a_7(2) = (2-1)^7 + (-1)^7 (2-1) = 1^7 - 1 = 0 $$

（あるいは、$7$ 個の環状の面を $2$ 色で交互に塗ることは奇数個のためできないので $0$ 通り、と考えてもよい）よって、この場合は $0$ 通りである。

以上（i）, （ii）より、

$$ P_4 = 504 + 0 = 504 $$

である。

解説

立体図形の塗り分け問題に見えますが、本質は「環状の塗り分け」です。 (2)で用いた「環状に並んだ $m$ 個のものを $r$ 色で塗り分ける方法」の公式 $a_m(r) = (r-1)^m + (-1)^m (r-1)$ は、難関大の確率や場合の数で頻出する漸化式処理です。「直線の塗り分け」から「両端が同色になる場合」を引くという考え方は、公式を忘れてもその場で導出できるようにしておきましょう。