名古屋大学 2017年 文系 第2問 解説

方針・初手

立方体の頂点を、出発点Aからの距離（あるいは位置関係）によって3つのグループに分類し、グループ間の遷移に着目して漸化式を立てる。頂点の対称性により、同じグループ内の頂点にいる確率はすべて等しいため、グループ全体にいる確率だけを追跡すればよい。

解法1

頂点を始点Aからの距離に応じて以下の3つのグループに分ける。 $V_1 = \{B, D, E\}$ $V_2 = \{C, F, H\}$ $V_3 = \{G\}$

問題の設定より、$p_n, q_n, r_n$ は、点Pが時刻 $n$ まで一度も頂点Aに戻らずに、それぞれ $V_1, V_2, V_3$ にいる確率である。 各点からの1回の移動先を考えると、以下のようになる。

• $V_1$ の各点（例えばB）からは、A, C, F に移動する。Aはグループ外、C, Fは $V_2$ に属するため、確率 $\frac{1}{3}$ でAへ、確率 $\frac{2}{3}$ で $V_2$ へ移動する。
• $V_2$ の各点（例えばC）からは、B, D, G に移動する。B, Dは $V_1$、Gは $V_3$ に属するため、確率 $\frac{2}{3}$ で $V_1$ へ、確率 $\frac{1}{3}$ で $V_3$ へ移動する。
• $V_3$ の点（G）からは、C, F, H に移動する。これらはすべて $V_2$ に属するため、確率 $1$ で $V_2$ へ移動する。

時刻 $0$ に点Pは頂点Aにおり、時刻 $1$ には必ず $V_1$ に移動する。 よって、$p_1 = 1$, $q_1 = 0$, $r_1 = 0$ である。

また、$n \geqq 1$ において、Aに戻らないという条件のもとで、確率の推移は以下の漸化式で表される。

$$p_{n+1} = \frac{2}{3} q_n$$

$$q_{n+1} = \frac{2}{3} p_n + r_n$$

$$r_{n+1} = \frac{1}{3} q_n$$

(1) 上の漸化式に $n=1, 2$ を代入して順に求める。 $n=1$ のとき、

$$p_2 = \frac{2}{3} q_1 = 0$$

$$q_2 = \frac{2}{3} p_1 + r_1 = \frac{2}{3} \cdot 1 + 0 = \frac{2}{3}$$

$$r_2 = \frac{1}{3} q_1 = 0$$

$n=2$ のとき、

$$p_3 = \frac{2}{3} q_2 = \frac{2}{3} \cdot \frac{2}{3} = \frac{4}{9}$$

$$q_3 = \frac{2}{3} p_2 + r_2 = 0 + 0 = 0$$

$$r_3 = \frac{1}{3} q_2 = \frac{1}{3} \cdot \frac{2}{3} = \frac{2}{9}$$

(2) (1)の漸化式から $p_n, r_n$ を消去して $q_n$ についての漸化式を作る。 $n \geqq 1$ に対して、

$$q_{n+2} = \frac{2}{3} p_{n+1} + r_{n+1}$$

$$q_{n+2} = \frac{2}{3} \left( \frac{2}{3} q_n \right) + \frac{1}{3} q_n = \frac{7}{9} q_n$$

よって、数列 $\{q_{2k-1}\}$ および $\{q_{2k}\}$ は、それぞれ公比 $\frac{7}{9}$ の等比数列となる。

(i) $n$ が奇数のとき

$n=2k-1$ （$k \geqq 2$ の自然数）とおく。$q_1 = 0$ であるから、すべての奇数 $n$ に対して $q_n = 0$ となる。 このとき、漸化式より $p_n, r_n$ は次のように求まる。

$$p_n = \frac{2}{3} q_{n-1} = \frac{2}{3} \cdot q_2 \left( \frac{7}{9} \right)^{\frac{n-1}{2}-1} = \frac{2}{3} \cdot \frac{2}{3} \left( \frac{7}{9} \right)^{\frac{n-3}{2}} = \frac{4}{9} \left( \frac{7}{9} \right)^{\frac{n-3}{2}}$$

$$r_n = \frac{1}{3} q_{n-1} = \frac{1}{3} \cdot \frac{2}{3} \left( \frac{7}{9} \right)^{\frac{n-3}{2}} = \frac{2}{9} \left( \frac{7}{9} \right)^{\frac{n-3}{2}}$$

(ii) $n$ が偶数のとき

$n=2k$ （$k \geqq 1$ の自然数）とおく。$q_2 = \frac{2}{3}$ であるから、

$$q_n = \frac{2}{3} \left( \frac{7}{9} \right)^{\frac{n}{2}-1}$$

このとき、漸化式より $n-1$ は奇数であるため $q_{n-1} = 0$ となり、

$$p_n = \frac{2}{3} q_{n-1} = 0$$

$$r_n = \frac{1}{3} q_{n-1} = 0$$

(3) 点Pが時刻 $2m$ で初めて頂点Aに戻るためには、時刻 $2m-1$ までの間一度もAに戻らずに $V_1$ （頂点B, D, Eのいずれか）におり、時刻 $2m-1$ から時刻 $2m$ の1回の移動でAへ移ればよい。 一度もAに戻らずに時刻 $2m-1$ に $V_1$ にいる確率は $p_{2m-1}$ であり、$V_1$ の各頂点からAに移動する確率は $\frac{1}{3}$ であるから、求める確率 $s_m$ は、

$$s_m = p_{2m-1} \times \frac{1}{3}$$

(i) $m=1$ のとき

$p_1 = 1$ であるから、

$$s_1 = 1 \times \frac{1}{3} = \frac{1}{3}$$

(ii) $m \geqq 2$ のとき

(2) で求めた $p_n$ の式に奇数 $n = 2m-1$ を代入して、

$$s_m = \frac{4}{9} \left( \frac{7}{9} \right)^{\frac{(2m-1)-3}{2}} \times \frac{1}{3} = \frac{4}{27} \left( \frac{7}{9} \right)^{m-2}$$

この式に $m=1$ を代入すると $\frac{4}{21}$ となり $s_1$ に一致しないため、$m=1$ の場合とはまとめて書けない。

解説

立方体上のランダムウォークの典型問題である。頂点群を出発点からの距離（対角線の位置関係）によって同値類にまとめ、各状態間の遷移確率を連立漸化式で表現するのが定石である。 また、立方体の頂点は二部グラフをなすため、移動回数が偶数か奇数かによって存在し得る頂点が明確に分かれる。このパリティ（偶奇性）に着目することで、多くの確率が $0$ になることが確認でき、計算過程の見通しが格段に良くなる。 (3) では、初めてAに戻るという条件を「1手前にAの隣にいる」という事象に読み替える。$m=1$ と $m \geqq 2$ で場合分けが生じるのは、漸化式の初項の振る舞いによるものである。

答え

(1) $p_2 = 0, q_2 = \frac{2}{3}, r_2 = 0$ $p_3 = \frac{4}{9}, q_3 = 0, r_3 = \frac{2}{9}$

(2) $n$ が偶数のとき：$p_n = 0, q_n = \frac{2}{3} \left( \frac{7}{9} \right)^{\frac{n}{2}-1}, r_n = 0$ $n$ が奇数のとき：$p_n = \frac{4}{9} \left( \frac{7}{9} \right)^{\frac{n-3}{2}}, q_n = 0, r_n = \frac{2}{9} \left( \frac{7}{9} \right)^{\frac{n-3}{2}}$

(3) $m = 1$ のとき $s_1 = \frac{1}{3}$ $m \geqq 2$ のとき $s_m = \frac{4}{27} \left( \frac{7}{9} \right)^{m-2}$