2005年前期京大理系第6問 - 数式で独楽する

先頭車両から順に1から $n$ まで番号のついた $n$ 両編成の列車がある。 $n \geqq 2$ とする。各車両を赤色、青色、黄色のいずれか1色で塗るとき、隣り合った車両の少なくとも一方が赤色となるような色の塗り方は何通りか。

解答例
解説

解答例

条件を満たす塗り方のうち、 $n$ 号車を赤と

するものを $a_n$ 通り
しないものを $b_n$ 通り

とします。

2両編成の場合、

2号車が赤なら、1号車の色は任意です。つまり3通りです。
2号車が青または黄の場合、1号車は必ず赤です。つまり2通りです。

したがって
\begin{eqnarray}
a_2 &=& 3 \tag{1} \\
b_2 &=& 2 \tag{2}
\end{eqnarray}です。

条件を満たす塗り方の $n$ 両編成の列車にもう1両を増やすことを考えます。

$n$ 号車が赤の場合、 $n +1$ 号車の色は任意です。
$n$ 号車が青や黄の場合、 $n +1$ 号車は必ず赤になります。

したがって、
\begin{eqnarray}
a_{n +1} &=& a_n +b_n \tag{3} \\
b_{n +1} &=& 2a_n \tag{4}
\end{eqnarray}が成り立ちます。

式(1) $-$ 式(2)より
\begin{equation}
a_{n +1} -b_{n +1} = -(a_n -b_n) \tag{5}
\end{equation}式(1)×2+式(2)より
\begin{equation}
2a_{n +1} +b_{n +1} = 2(2a_n +b_n) \tag{6}
\end{equation}を得ます。

式(1), (2), (5), (6)より、
\begin{eqnarray}
a_n -b_n &=& (-1)^{n -2}(a_2 -b_2) &=& (-1)^n \tag{7} \\
2a_n +b_n &=& 2^{n -2}(2a_2 +b_2) &=& 2^{n +1} \tag{8}
\end{eqnarray}となります。

式(7), (8)より、
\begin{eqnarray}
a_n &=& \frac{2^{n +1} +(-1)^n}{3} \\
b_n &=& \frac{2^{n +1} -2 (-1)^n}{3}
\end{eqnarray}を得ます。
よって、求める色の塗り方は
\begin{equation}
a_n +b_n = \frac{2^{n +2} -(-1)^n}{3}
\end{equation}通りとなります。

解説

条件を満たす塗り方を直接求めるのは私には無理でした。
ならば、条件を満たす塗り方をしている状態から、1両増やしてもなお条件を満たしている状態を考えることになります。つまり漸化式を組むことになります。