$n$両編成の列車があり、各車両を赤、青、黄のいずれかの色で塗る。ただし、隣り合った車両の少なくとも一方が赤色となるように塗る方法は何通りあるか。$n \ge 2$。

1. 問題の内容

$n$両編成の列車があり、各車両を赤、青、黄のいずれかの色で塗る。ただし、隣り合った車両の少なくとも一方が赤色となるように塗る方法は何通りあるか。$n \ge 2$。

2. 解き方の手順

まず、$a_n$ を $n$ 両の列車に対する条件を満たす塗り方の総数とする。

$n=1$ の場合、$a_1 = 3$ (赤、青、黄)。

$n=2$ の場合、両方とも赤でない場合は青青、青黄、黄青、黄黄の4通り。全体は$3^2 = 9$通りなので、$9-4 = 5$ 通りある。

隣り合う車両の少なくとも一方が赤であるという条件を満たさない塗り方は、全ての車両が赤色以外（青または黄）で塗られている場合である。

$a_n$を求める漸化式を考える。

$n$両目が赤の場合、前の $n-1$ 両はどのような塗り方でも条件を満たすので、$a_{n-1}$ 通り。

$n$両目が赤でない場合（青または黄）、 $n-1$ 両目は必ず赤でなければならない。

このとき、$n-2$ 両はどのような塗り方でも条件を満たすので、$a_{n-2}$ 通り。

よって、$n$両目が赤でない塗り方は $2 a_{n-2}$ 通り。

したがって、漸化式は $a_n = a_{n-1} + 2 a_{n-2}$ となる。

初期条件は、$a_1 = 3$, $a_2 = a_1 + 2 a_0 = 3+2\times \frac{3}{1}$ から求めることができず、$a_2 = 5$。

別の考え方として、全体から条件を満たさないものを引くことを考える。

$n$両全体を赤、青、黄で塗る方法は $3^n$ 通り。

条件を満たさないのは、隣り合う車両がどちらも赤でない場合、つまり全ての車両が青または黄で塗られている場合である。

この場合、隣り合う車両がどちらも赤でないように塗る方法は、2色の塗り分けになる。

これを $b_n$ とする。すると、$b_1 = 2$, $b_2 = 1$.

隣り合う車両が赤でない塗り方の総数 $b_n$ について考える。

$b_n$ を、$n$ 両全てが青か黄で塗られている場合の数とする。隣り合う車両がどちらも赤でない場合、各車両は青か黄のいずれかで塗られるので、$b_n = 2^n$ である。条件より、少なくとも一方が赤であるという条件の否定は、どちらも赤ではないなので、全ての車両が青か黄であれば良い。しかし、これは明らかに間違いである。

$b_1=2$, $b_2 = 4$. この時の条件を満たす塗り方は5通り。$a_2=3^2-2\times2 =5$

漸化式を用いた$b_n$ の導出を試みる。

$n$番目が青または黄の場合、$n-1$番目も青または黄である必要がある。$b_n = 2 b_{n-1}$.

これは$2^n$となるのでやはり間違いである。

条件を満たす塗り方の総数 $a_n$ は、すべての車両を赤色、青色、黄色のいずれか一色で塗る塗り方の総数 $3^n$ から、隣り合った車両がどちらも赤色ではないような塗り方を引いたものになる。

隣り合った車両がどちらも赤色ではない塗り方を $c_n$ とする。

すると、漸化式は $a_n = 3^n - c_n$ となる。

$c_n$ を求めることを考える。

$c_1 = 2$ (青、黄)

$c_2 = 4$ (青青、青黄、黄青、黄黄)

$c_n = 2 c_{n-1}$ これは間違い。

$n$両目が青か黄の場合を考える。

$a_1=3$, $a_2=5$, $a_3=a_2 + 2a_1 = 5 + 2(3)=11$.

$n=3$の場合、赤を含まないのは $2^3=8$ 通り。青青青、青青黄、青黄青、青黄黄、黄青青、黄青黄、黄黄青、黄黄黄

条件を満たさないのは、青青青、青青黄、青黄青、黄青青、黄黄黄。 よって$3^3-8$は間違い。

$a_n = a_{n-1} + 2a_{n-2}$。

$a_1=3$, $a_2=5$

$a_3 = 5 + 2 \times 3 = 11$

$a_4 = 11 + 2 \times 5 = 21$

$a_5 = 21 + 2 \times 11 = 43$

3. 最終的な答え

$a_n = a_{n-1} + 2a_{n-2}$ ただし、$a_1=3$, $a_2=5$