京都大学 2005年度理系数学第6問解答・解説

問題

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

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

方針

条件は「赤でない車両が隣り合ってはいけない」と読み替えられる。末尾の色で場合分けし，条件を満たす塗り方全体を $a_{n}$ ，最後が赤のものを $r_{n}$ ，最後が赤でないものを $s_{n}$ とおく。最後が赤なら前 $n$ 両は任意の条件付き塗り方，最後が赤でないなら直前は赤で，最後の色は青・黄の2通りである。これにより $a_{n + 1} = a_{n} + 2 a_{n - 1}$ を導き，初期値 $a_{1} = 3, a_{2} = 5$ から一般項を求める。別解として，赤でない車両の位置を隣り合わないように選ぶ方法でも数えられる。

解答

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

条件を満たす $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} = 2 r_{n}$ である。さらに $r_{n} = a_{n - 1}$ なので $s_{n + 1} = 2 a_{n - 1}$ である。

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

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

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

別解。赤でない車両の位置を先に選ぶこともできる。赤でない車両が $j$ 両あるとき，それらは隣り合ってはいけない。 $n$ 個の位置から隣り合わない $j$ 個を選ぶ方法は $_{n - j + 1} C_{j}$ 通りであり，選ばれた各車両は青または黄色の2通りに塗れる。したがって塗り方の総数は $\sum_{j ≧ 0}_{n - j + 1} C_{j} 2^{j}$ である。この和も同じ漸化式 $a_{n + 1} = a_{n} + 2 a_{n - 1}$ と初期値 $a_{1} = 3, a_{2} = 5$ を満たすので，上で求めた $\frac{2 ^{n + 2} - ( - 1 ) ^{n}}{3}$ に一致する。

京都大学 2005年度理系数学 第6問

問題

方針

解答

京都大学 2005年度
理系数学第6問