京都大学 2005年 理系 第6問 解説

方針・初手

「隣り合った車両の少なくとも一方が赤色」という条件は、「赤色以外の車両（青色または黄色）は隣り合ってはいけない」と言い換えることができます。

車両数が $n$ と一般化されているため、先頭から順に色を決めていく漸化式を利用して考えるのが定石です。直前の車両の色が「赤色」か「青・黄色」かによって次に塗れる色の選択肢が変わるため、この2つの状態に分けて連立漸化式を立てる方法（解法1）と、末尾の色の並びに着目して直接3項間漸化式を立てる方法（解法2）の2つを紹介します。

解法1

$k$ 両編成の列車のうち条件を満たす塗り方の総数を $c_k$ 通りとし、最後尾が赤色である塗り方を $a_k$ 通り、青色または黄色である塗り方を $b_k$ 通りとする。$c_k = a_k + b_k$。

$k+1$ 両目の色を決める場合：

• $k+1$ 両目が赤色の場合：$k$ 両目は何色でもよいから $a_{k+1} = c_k$
• $k+1$ 両目が青・黄の場合：$k$ 両目は必ず赤色でなければならないから $b_{k+1} = 2a_k$

$$ c_{k+1} = a_{k+1} + b_{k+1} = c_k + 2a_k $$

$k \geqq 2$ のとき $a_k = c_{k-1}$ であるから、

$$ c_{n+2} = c_{n+1} + 2c_n \quad (n \geqq 1) $$

初期条件： $c_1 = 3$（赤・青・黄の3通り）、$c_2 = 9 - 4 = 5$（（青,青）（黄,黄）（青,黄）（黄,青）の4通りを除く）

特性方程式 $\lambda^2 - \lambda - 2 = 0$ の解は $\lambda = 2, -1$。漸化式を変形すると、

$$ c_{n+1} - 2c_n = -(c_n - 2c_{n-1}) \quad \cdots \text{①} $$

$$ c_{n+1} + c_n = 2(c_n + c_{n-1}) \quad \cdots \text{②} $$

①より $c_{n+1} - 2c_n = (-1) \cdot (-1)^{n-1} = (-1)^n$、②より $c_{n+1} + c_n = 8 \cdot 2^{n-1} = 2^{n+2}$。

これらから、

$$ 3c_n = 2^{n+2} - (-1)^n \implies c_n = \frac{2^{n+2} + (-1)^{n+1}}{3} $$

解法2

$k$ 両編成の塗り方の総数を $x_k$ 通りとする（$k \geqq 3$）。

最後尾（$k$ 両目）の色で場合分けする。

• 最後尾が赤色の場合： 直前の $k-1$ 両は条件を満たす任意の塗り方でよいから $x_{k-1}$ 通り。
• 最後尾が青・黄の場合： 直前の $k-1$ 両目は必ず赤色で、その前の $k-2$ 両は条件を満たす任意の塗り方。よって $x_{k-2} \times 1 \times 2 = 2x_{k-2}$ 通り。

$$ x_k = x_{k-1} + 2x_{k-2} \quad (k \geqq 3) $$

$x_1 = 3$、$x_2 = 5$ を初期条件として、解法1と同様に解くと、

$$ x_n = \frac{2^{n+2} + (-1)^{n+1}}{3} $$

解説

$n$ 個のものが一列に並ぶ状態を考える際、全体の総数をまとめて数え上げようとすると場合分けが複雑になりがちです。このようなときは、要素を1つ追加するときの「変化の規則」に着目し、漸化式を立てる手法が非常に有効です。

解法1のように状態を2種類（末尾が赤か否か）に分けて連立漸化式を立てるアプローチは汎用性が高く、解法2のようにブロック単位で直接3項間漸化式を立てるアプローチは記述がすっきりします。

答え

$$ \frac{2^{n+2} + (-1)^{n+1}}{3} \text{ 通り} $$