京都大学 2005年度 前期日程 第2次学力試験理系数学 第6問

条件「隣り合った車両の少なくとも一方が赤色」とは，青または黄色の車両が隣り合ってはいけない，ということである。

条件を満たす $n$ 両の塗り方の総数を $a_n$ とする。また，最後の車両が赤であるものを $r_n$ 通り，最後の車両が赤でないものを $s_n$ 通りとする。すると $a_n=r_n+s_n$ である。 $n+1$ 両の塗り方を考える。最後の車両が赤である場合，その直前の車両の色には追加の制限はない。したがって，前の $n$ 両は条件を満たす任意の塗り方でよく，$r_{n+1}=a_n$ である。

最後の車両が赤でない場合，最後の色は青または黄色の2通りである。このとき隣り合う $n$ 番目の車両は赤でなければならない。したがって，$n$ 番目までの塗り方は「最後が赤」である条件付きの塗り方であり，$s_{n+1}=2r_n$ である。さらに $r_n=a_{n-1}$ なので $s_{n+1}=2a_{n-1}$ である。

よって $$a_{n+1}=r_{n+1}+s_{n+1}=a_n+2a_{n-1}$$ を得る。初期値は $a_1=3$ である。また2両の場合，全9通りのうち，両方とも赤でない $2\cdot 2=4$ 通りが条件に反するので $a_2=9-4=5$ である。

漸化式 $a_{n+1}=a_n+2a_{n-1}$ は $$a_{n+1}-2a_n=-(a_n-2a_{n-1})$$ と書けるので，一般項は $2^n$ と $(-1{)}^n$ の組合せになる。実際 $$a_n=A\cdot 2^n+B\cdot (-1{)}^n$$ とおくと，初期値から $2A-B=3,4A+B=5$ である。これを解くと $$A={\displaystyle \frac{4}{3}},B=-{\displaystyle \frac{1}{3}}$$ である。したがって $$a_n={\displaystyle \frac{4}{3}}\cdot 2^n-{\displaystyle \frac{1}{3}}(-1{)}^n={\displaystyle \frac{2^{n+2}-(-1{)}^n}{3}}$$ である。

よって求める塗り方の数は ${\displaystyle \frac{2^{n+2}-(-1{)}^n}{3}}$ 通りである。

赤でない車両の位置を，互いに隣り合わないように先に選ぶ。位置の選び方と青・黄の選び方を掛け，得られた和が同じ漸化式を満たすことを確認する。

赤でない車両が $j$ 両あるとする。その位置は互いに隣り合ってはならない。

選んだ位置を$$1\leqq p_1<p_2<\cdots <p_j\leqq n,p_{r+1}\geqq p_r+2$$とする。$q_r=p_r-(r-1)$ と変換すると$$1\leqq q_1<q_2<\cdots <q_j\leqq n-j+1$$となる。したがって位置の選び方は$${\displaystyle \frac{(n-j+1)!}{j!(n-2j+1)!}}$$通りである。選ばれた各車両は青または黄色の2通りに塗れるから，総数は$$\sum _{j=0}^{\lfloor {\displaystyle \frac{n+1}{2}}\rfloor }{\displaystyle \frac{(n-j+1)!}{j!(n-2j+1)!}}{2}^j$$である。

この数を $b_n$ とおく。末尾が赤なら前の $n-1$ 両は任意であり，末尾が赤でないなら直前は赤で，末尾の色は2通りだから$$b_n=b_{n-1}+2b_{n-2}$$を満たす。さらに $b_1=3,b_2=5$ である。したがって解法1と同じ漸化式・初期値をもち，$$b_n={\displaystyle \frac{2^{n+2}-(-1{)}^n}{3}}$$を得る。