京都大学 2022年度文系数学第2問解答・解説

問題

下図の三角柱 $A B C - D E F$ において， $A$ を始点として，辺に沿って頂点を $n$ 回移動する．すなわち，この移動経路

P_{0} \to P_{1} \to P_{2} \to \dots \to P_{n - 1} \to P_{n} (ただし P_{0} = A)

において， $P_{0} P_{1}, P_{1} P_{2}, \dots, P_{n - 1} P_{n}$ はすべて辺であるとする．また，同じ頂点を何度通ってもよいものとする．このような移動経路で，終点 $P_{n}$ が $A, B, C$ のいずれかとなるものの総数 $a_{n}$ を求めよ．

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

方針

解法1

三角柱の6頂点を、 $A, B, C$ 側にいる状態と $D, E, F$ 側にいる状態の2種類にまとめる。各頂点からは、同じ三角形内の頂点へ進む辺が2本、反対側の対応する頂点へ進む辺が1本出ている。したがって、終点が上側にある経路数 $a_{n}$ と下側にある経路数 $b_{n}$ は2本の漸化式を満たす。和は全経路数 $3^{n}$ 、差は不変であることから $a_{n}$ を求める。

解法2

各移動を「同じ三角形内の辺」と「対応頂点へ渡る辺」に分類する。終点が $A, B, C$ 側にあるためには渡る辺を使う回数が偶数である。渡る回の位置を選び、残りの各回には同じ側で2通りの選択があるので、二項定理の偶数項和を使う。

解答

解法1

終点が $A, B, C$ のいずれかである経路数を $a_{n}$ 、終点が $D, E, F$ のいずれかである経路数を $b_{n}$ とする。初期状態は $P_{0} = A$ であるから $a_{0} = 1, b_{0} = 0$ である。

三角柱の各頂点からは、同じ三角形内の別の2頂点へ向かう辺が2本あり、反対側の対応する頂点へ向かう辺が1本ある。したがって、 $n$ 回移動後に上側 $A, B, C$ にいる経路からは、次の1回で上側へ行くものが2通り、下側へ行くものが1通りである。同様に、下側にいる経路からは、次の1回で上側へ行くものが1通り、下側へ行くものが2通りである。

よって $a_{n + 1} = 2 a_{n} + b_{n}, b_{n + 1} = a_{n} + 2 b_{n}$ が成り立つ。

まず和をとると $a_{n + 1} + b_{n + 1} = 3 (a_{n} + b_{n})$ である。 $a_{0} + b_{0} = 1$ だから $a_{n} + b_{n} = 3^{n}$ である。これは、各回の移動先が常に3通りあることとも一致する。

次に差をとると $a_{n + 1} - b_{n + 1} = a_{n} - b_{n}$ である。したがって $a_{n} - b_{n}$ は一定で、初期値より $a_{n} - b_{n} = a_{0} - b_{0} = 1$ である。

以上の2式 $a_{n} + b_{n} = 3^{n}, a_{n} - b_{n} = 1$ を加えると $2 a_{n} = 3^{n} + 1$ である。よって求める総数は $a_{n} = \frac{3 ^{n} + 1}{2}$ である。

解法2

1回の移動には、現在いる三角形の内部で別の頂点へ進む2通りと、反対側の対応する頂点へ渡る1通りがある。

$D, E, F$ 側へ渡る辺を使った回数を $k$ とする。出発点は $A, B, C$ 側なので、 $n$ 回後にも $A, B, C$ 側にいるための必要十分条件は $k$ が偶数である。

渡る $k$ 回の位置は $_{n} C_{k}$ 通りに選べる。残りの $n - k$ 回は、その時いる三角形内で2本の辺から選ぶので $2^{n - k}$ 通りである。したがって

a_{n} = 0 ≦ k ≦ n k は偶数 \sum_{n} C_{k} 2^{n - k} .

二項定理より

3^{n} = (2 + 1)^{n} = k = 0 \sum n_{n} C_{k} 2^{n - k},

1 = (2 - 1)^{n} = k = 0 \sum n (- 1)^{k}_{n} C_{k} 2^{n - k} .

この2式を加えると奇数 $k$ の項が消え、偶数 $k$ の項が2倍になる。よって

2 a_{n} = 3^{n} + 1, a_{n} = \frac{3 ^{n} + 1}{2}

である。

京都大学 2022年度文系数学 第2問

問題

方針

解法1

解法2

解答

解法1

解法2

京都大学 2022年度
文系数学第2問