トップ› 名古屋大学› 2000年› 理系第3問

名古屋大学 2000年理系第3問解説

方針・初手

(1), (2) は確率ではなく「経路数」を求める問題であることに注意する。点 $A_n$ や $B_n$ に到達する直前の状態を場合分けし、漸化式を立てる。 (3) は確率の計算である。「等確率で移動」という条件から、各分岐点でどの移動を選ぶかを追う。移動を「1つの列から次の列への進行」という単位で捉え直すと、縦移動（$A \leftrightarrow B$）の有無による独立な試行の繰り返しとみなすことができ、見通しよく解くことができる。

解法1

(1), (2)

点 $A_n$ への到達経路数を $a_n$、点 $B_n$ への到達経路数を $b_n$ とする。 $P$ の移動規則より、点に到達した直後は「前にいた点には戻らない」。 $A_n$ に到達する直前の点は $A_{n-1}$ または $B_n$ のいずれかである。

$A_{n-1}$ を経由して $A_n$ に到る経路は、$A_{n-1}$ までの経路に $A_{n-1} \to A_n$ を繋げたものであり、$a_{n-1}$ 通りある。
$B_n$ を経由して $A_n$ に到る経路は、直前が $B_{n-1} \to B_n$ と移動した場合のみ可能である（$A_n \to B_n \to A_n$ は戻る移動になり不可）。したがって、$B_{n-1}$ までの経路に $B_{n-1} \to B_n \to A_n$ を繋げたものであり、$b_{n-1}$ 通りある。

よって、次の漸化式が成り立つ。

$$ a_n = a_{n-1} + b_{n-1} \quad (n \ge 1) $$

同様に、$B_n$ に到達する直前の点は $B_{n-1}$ または $A_n$ であり、

$B_{n-1}$ を経由する経路は $b_{n-1}$ 通りある。
$A_n$ を経由する経路は、直前が $A_{n-1} \to A_n$ と移動した場合のみ可能なので、$a_{n-1}$ 通りある。

よって、次の漸化式が成り立つ。

$$ b_n = b_{n-1} + a_{n-1} \quad (n \ge 1) $$

初期状態 $n=0$ について、出発点は $A_0$ であるから $A_0$ への行き方は $a_0 = 1$。また $B_0$ への行き方は $A_0 \to B_0$ のみであるから $b_0 = 1$ となる。これより順に計算すると、

$$ \begin{aligned} a_1 &= 1 + 1 = 2, & b_1 &= 1 + 1 = 2 \\ a_2 &= 2 + 2 = 4, & b_2 &= 2 + 2 = 4 \\ a_3 &= 4 + 4 = 8, & b_3 &= 4 + 4 = 8 \end{aligned} $$

したがって、(1) の答えは $a_3 = 8, b_3 = 8$。また、数列 $\{a_n\}, \{b_n\}$ はともに初項2、公比2の等比数列となるため、(2) の答えは $a_n = 2^n, b_n = 2^n$ ($n \ge 1$) となる。

(3)

$P$ の移動を「$i-1$ 列目から $i$ 列目への遷移」として考える。 $P$ が $i-1$ 列目の点（$A_{i-1}$ または $B_{i-1}$）に初めて到達した状態から、$i$ 列目の点（$A_i$ または $B_i$）に初めて到達するまでの移動は、次のいずれかである。

直進（横移動のみ）：確率 $\frac{1}{2}$ で同じ文字の点に進む。所要時間は 1秒。
曲がる（縦移動を伴う）：確率 $\frac{1}{2}$ で違う文字の点に進む。例えば $A_{i-1} \to B_{i-1} \to B_i$ のように移動し、所要時間は 2秒。

初期の $0$ 列目から $1$ 列目への遷移も、$A_0$ から確率 $\frac{1}{2}$ で $A_1$ (所要時間1秒)、確率 $\frac{1}{2}$ で $B_0 \to B_1$ (所要時間2秒) と移動するので同じ構造である。これらは各列への遷移ごとに独立に選択される。

$0$ 列目から $k$ 列目に入るまでの $k$ 回の遷移のうち、縦移動した回数を $j$ ($0 \le j \le k$) とすると、その事象が起こる確率は ${}_k \mathrm{C}_{j} \left(\frac{1}{2}\right)^k$ であり、$k$ 列目に初めて到達するまでの総時間は $k + j$ 秒である。また、初期位置が $A$ 側であるため、到達した点は縦移動の回数 $j$ の偶奇で決まり、

$j$ が偶数のとき：$A_k$ に到達する
$j$ が奇数のとき：$B_k$ に到達する

一方、$Q$ は $A_8$ から毎秒 $A_7, A_6, \dots$ と移動するため、時刻 $t$ に $A_{8-t}$ にいる。 $P$ と $Q$ が $A_k$ で出会うのは、$P$ が $A_k$ に到達する時刻が $8-k$ のときである。

(i) $j$ が偶数の経路の場合

$P$ は時刻 $k+j$ に $A_k$ に到達する。出会う条件は $k+j = 8-k$ より $j = 8-2k$。 $0 \le j \le k$ より $0 \le 8-2k \le k$、これを満たす整数 $k$ は $k=3, 4$。

$k=4$ のとき $j=0$ (偶数)。確率は ${}_4 \mathrm{C}_{0} \left(\frac{1}{2}\right)^4 = \frac{1}{16}$
$k=3$ のとき $j=2$ (偶数)。確率は ${}_3 \mathrm{C}_{2} \left(\frac{1}{2}\right)^3 = \frac{3}{8}$

(ii) $j$ が奇数の経路の場合

$P$ は時刻 $k+j$ に $B_k$ に到達する。ここから $A_k$ に移動して出会うには、さらに確率 $\frac{1}{2}$ で $B_k \to A_k$ へ移動する必要がある。このとき $A_k$ に到達する時刻は $k+j+1$ 秒となる。出会う条件は $k+j+1 = 8-k$ より $j = 7-2k$。 $0 \le j \le k$ より $0 \le 7-2k \le k$、これを満たす整数 $k$ は $k=3$。

$k=3$ のとき $j=1$ (奇数)。確率は ${}_3 \mathrm{C}_{1} \left(\frac{1}{2}\right)^3 \times \frac{1}{2} = \frac{3}{16}$

これらは互いに排反であるから、求める確率は

$$ \frac{1}{16} + \frac{3}{8} + \frac{3}{16} = \frac{5}{8} $$

解説

(1), (2) は経路数のカウントであり、(3) は確率の問題であることに注意したい。「等確率で移動」という条件から、すべての経路が等確率で実現するわけではないため、経路数と確率の混同を避ける必要がある。 (3) では、点ごとの微視的な状態遷移を追うと場合分けが複雑になりやすいが、「列から列への進行」という巨視的なブロックで捉え直すことで、縦移動の有無という独立試行の反復（二項分布のモデル）に帰着でき、計算の見通しが非常に良くなる。