トップ› 京都大学› 2022年› 文系第2問

京都大学 2022年文系第2問解説

方針・初手

$n$ 回移動した後の終点が、上の面（頂点 $A, B, C$）にある経路の総数 $a_n$ を求める問題です。直接 $a_n$ を求めるのは難しいため、下の面（頂点 $D, E, F$）にある経路の総数を $b_n$ とおき、1回の移動で状態がどう変化するかを考えて $a_n$ と $b_n$ の連立漸化式を立てるのが定石です。

解法1

終点 $P_n$ が頂点 $A, B, C$ のいずれかとなる経路の総数を $a_n$ とする。また、終点 $P_n$ が頂点 $D, E, F$ のいずれかとなる経路の総数を $b_n$ とする。

$n$ 回目の移動後、$P_n$ が頂点 $A, B, C$ のいずれかにあるとする。次の $n+1$ 回目の移動では、

同じ面（上の面）の他の2頂点のいずれかに移動する（2通り）
対応する下の面の頂点に移動する（1通り）

のいずれかである。$P_n$ が頂点 $D, E, F$ のいずれかにある場合も同様に、次の移動では、

同じ面（下の面）の他の2頂点のいずれかに移動する（2通り）
対応する上の面の頂点に移動する（1通り）

したがって、$n$ 回目の状態から $n+1$ 回目の状態への遷移について、以下の連立漸化式が成り立つ。

$$ \begin{cases} a_{n+1} = 2a_n + b_n & \cdots ① \\ b_{n+1} = a_n + 2b_n & \cdots ② \end{cases} $$

①と②の辺々を足すと、

$$ a_{n+1} + b_{n+1} = 3(a_n + b_n) $$

数列 $\{a_n + b_n\}$ は、初項 $a_0 + b_0$、公比 $3$ の等比数列である。始点 $P_0$ は $A$ であるから、$a_0 = 1, b_0 = 0$ である。よって、$a_0 + b_0 = 1$ より、

$$ a_n + b_n = 1 \cdot 3^n = 3^n \quad \cdots ③ $$

また、①から②の辺々を引くと、

$$ a_{n+1} - b_{n+1} = a_n - b_n $$

数列 $\{a_n - b_n\}$ は、初項 $a_0 - b_0 = 1 - 0 = 1$、公比 $1$ の等比数列（すなわち常に一定）である。よって、

$$ a_n - b_n = 1 \quad \cdots ④ $$

③と④の辺々を足し合わせると、

$$ 2a_n = 3^n + 1 $$

$$ a_n = \frac{3^n + 1}{2} $$

解法2

$n$ 回移動したときのすべての経路の総数について考える。各頂点からは常に3本の辺が出ているため、どの頂点にいても次の移動先は3通りある。したがって、$n$ 回移動したときの経路の総数は $3^n$ 通りである。

終点 $P_n$ が頂点 $A, B, C$ のいずれかとなる経路の総数を $a_n$、頂点 $D, E, F$ のいずれかとなる経路の総数を $b_n$ とすると、

$$ a_n + b_n = 3^n $$

が成り立つ。

また、$P_n$ が頂点 $A, B, C$ のいずれかとなるのは、・$P_{n-1}$ が $A, B, C$ のいずれかであり、そこから上の面の他の頂点に移動する場合（$2a_{n-1}$ 通り）・$P_{n-1}$ が $D, E, F$ のいずれかであり、そこから上の面の頂点に移動する場合（$b_{n-1}$ 通り）の和であるから、

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

が成り立つ。

ここに $b_{n-1} = 3^{n-1} - a_{n-1}$ を代入すると、

$$ \begin{aligned} a_n &= 2a_{n-1} + (3^{n-1} - a_{n-1}) \\ a_n &= a_{n-1} + 3^{n-1} \end{aligned} $$

すなわち

$$ a_n - a_{n-1} = 3^{n-1} \quad (n \ge 1) $$

となり、数列 $\{a_n\}$ の階差数列が $\{3^{n-1}\}$ であることがわかる。

$n \ge 1$ のとき、始点 $P_0$ は $A$ であり $a_0 = 1$ であるから、

$$ \begin{aligned} a_n &= a_0 + \sum_{k=1}^n 3^{k-1} \\ &= 1 + \frac{1(3^n - 1)}{3 - 1} \\ &= 1 + \frac{3^n - 1}{2} \\ &= \frac{3^n + 1}{2} \end{aligned} $$

これは $n=0$ のときも $a_0 = \frac{1+1}{2} = 1$ となり成り立つ。

解説

立体図形上を移動する点の経路数を求める典型的な問題です。すべての頂点を個別に扱うのではなく、対称性に着目して「上の面のグループ」「下の面のグループ」のように状態をまとめて漸化式を立てるのがポイントです。解法1のように連立漸化式を立てて和と差をとる方法は、対称的な推移確率のマルコフ連鎖（確率漸化式）などでも頻出する非常に重要な処理です。解法2のように、全事象の数が $3^n$ であることを利用して一方の変数を消去し、階差数列の形に持ち込むのも見通しの良い優れた解法となります。