トップ› 名古屋大学› 1998年› 文系第2問

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

方針・初手

点 $Q$ が $n$ 秒後に各頂点にいる確率を数列として設定し、推移確率の漸化式を立てる。 $x$ 軸平行・$y$ 軸平行な移動が具体的にどの頂点間の移動を指すかを確認し、隣接する頂点への推移を定式化する。また、移動のたびに「頂点 $A, C$ のグループ」と「頂点 $B, D$ のグループ」を交互に行き来することに注目する。

解法1

頂点 $A(0,1), B(0,0), C(1,0), D(1,1)$ の配置から、

$x$ 軸に平行な移動（確率 $p$）: 頂点 $A$ と $D$ の間、および頂点 $B$ と $C$ の間
$y$ 軸に平行な移動（確率 $1-p$）: 頂点 $A$ と $B$ の間、および頂点 $C$ と $D$ の間となる。

点 $Q$ が $n$ 秒後に頂点 $A, B, C, D$ にいる確率をそれぞれ $a_n, b_n, c_n, d_n$ とする。推移のルールより、以下の関係式が成り立つ。

$$ \begin{cases} a_{n+1} = (1-p)b_n + p d_n \\ b_{n+1} = (1-p)a_n + p c_n \\ c_{n+1} = p b_n + (1-p)d_n \\ d_{n+1} = p a_n + (1-p)c_n \end{cases} $$

初期状態は最初に頂点 $A$ にいるため、$a_0 = 1, b_0 = 0, c_0 = 0, d_0 = 0$ である。

(1)

$n=0$ のときの確率を漸化式に代入すると、

$$ a_1 = 0, \quad b_1 = 1-p, \quad c_1 = 0, \quad d_1 = p $$

$n=1$ のときの確率を代入すると、

$$ \begin{aligned} a_2 &= (1-p)b_1 + p d_1 = (1-p)^2 + p^2 = 2p^2 - 2p + 1 \\ b_2 &= (1-p)a_1 + p c_1 = 0 \\ c_2 &= p b_1 + (1-p)d_1 = p(1-p) + (1-p)p = -2p^2 + 2p \\ d_2 &= p a_1 + (1-p)c_1 = 0 \end{aligned} $$

よって、$a_2 = 2p^2 - 2p + 1$、$c_2 = -2p^2 + 2p$ である。

さらに $n=2$ のときの確率を代入すると、

$$ a_3 = 0, \quad b_3 = (1-p)a_2 + p c_2, \quad c_3 = 0, \quad d_3 = p a_2 + (1-p)c_2 $$

これを用いて $n=3$ の式に代入すると、

$$ \begin{aligned} a_4 &= (1-p)b_3 + p d_3 \\ &= (1-p) \{ (1-p)a_2 + p c_2 \} + p \{ p a_2 + (1-p)c_2 \} \\ &= \{ (1-p)^2 + p^2 \} a_2 + 2p(1-p) c_2 \\ &= a_2^2 + c_2^2 \end{aligned} $$

$$ \begin{aligned} c_4 &= p b_3 + (1-p)d_3 \\ &= p \{ (1-p)a_2 + p c_2 \} + (1-p) \{ p a_2 + (1-p)c_2 \} \\ &= 2p(1-p) a_2 + \{ p^2 + (1-p)^2 \} c_2 \\ &= c_2 a_2 + a_2 c_2 \\ &= 2 a_2 c_2 \end{aligned} $$

ここで、$a_2 = 2p^2 - 2p + 1$、$c_2 = -2p^2 + 2p$ を代入して展開する。

$$ \begin{aligned} a_4 &= (2p^2 - 2p + 1)^2 + (-2p^2 + 2p)^2 \\ &= (4p^4 - 8p^3 + 8p^2 - 4p + 1) + (4p^4 - 8p^3 + 4p^2) \\ &= 8p^4 - 16p^3 + 12p^2 - 4p + 1 \end{aligned} $$

$$ \begin{aligned} c_4 &= 2 (2p^2 - 2p + 1)(-2p^2 + 2p) \\ &= 2 (-4p^4 + 4p^3 + 4p^3 - 4p^2 - 2p^2 + 2p) \\ &= -8p^4 + 16p^3 - 12p^2 + 4p \end{aligned} $$

(2)

(1) の議論を一般化する。漸化式を用いて $a_{n+2}$ を表すと、

$$ \begin{aligned} a_{n+2} &= (1-p)b_{n+1} + p d_{n+1} \\ &= (1-p) \{ (1-p)a_n + p c_n \} + p \{ p a_n + (1-p)c_n \} \\ &= \{ (1-p)^2 + p^2 \} a_n + 2p(1-p) c_n \\ &= (2p^2 - 2p + 1) a_n + (-2p^2 + 2p) c_n \end{aligned} $$

ここで、点 $Q$ は $1$ 秒ごとに隣接する頂点へ移動するため、$n$ が偶数のときは必ず頂点 $A$ または $C$ にいる。したがって、$a_{2n} + c_{2n} = 1$ が成り立つ。これを用いて $c_{2n}$ を消去すると、

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

この2項間漸化式を変形する。特性方程式 $x = (2p-1)^2 x - 2p^2 + 2p$ を解くと、

$$ \begin{aligned} \{ 1 - (4p^2 - 4p + 1) \} x &= -2p(p - 1) \\ 4p(1-p) x &= 2p(1-p) \end{aligned} $$

(i) $p(1-p) \neq 0$ すなわち $p \neq 0, 1$ のとき

$x = \frac{1}{2}$ となり、漸化式は次のように変形できる。

$$ a_{2n+2} - \frac{1}{2} = (2p - 1)^2 \left( a_{2n} - \frac{1}{2} \right) $$

数列 $\left\{ a_{2n} - \frac{1}{2} \right\}$ は初項 $a_0 - \frac{1}{2} = 1 - \frac{1}{2} = \frac{1}{2}$、公比 $(2p - 1)^2$ の等比数列であるから、

$$ a_{2n} - \frac{1}{2} = \frac{1}{2} \{ (2p - 1)^2 \}^n = \frac{1}{2} (2p - 1)^{2n} $$

よって、次が成り立つ。

$$ a_{2n} = \frac{1}{2} \{ 1 + (2p - 1)^{2n} \} $$

(ii) $p = 0$ または $p = 1$ のとき

漸化式は $a_{2n+2} = a_{2n}$ となり、$a_0 = 1$ より常に $a_{2n} = 1$ である。これは (i) で求めた式に $p=0, 1$ を代入した場合（$\frac{1}{2} \{ 1 + (\mp 1)^{2n} \} = 1$）と一致する。したがって、すべての $p$ について成り立つ。

解説

確率の推移を扱う問題では、$n$ 秒後の状態を各々文字でおき、連立漸化式を立てるのが定石である。本問のように「1回の移動で必ず隣の点に行く」設定では、到達可能な点が偶奇で分かれること（市松模様のような性質）に気づくことが重要である。これを利用して $a_{2n} + c_{2n} = 1$ とすることで、実質的に2状態の推移に帰着でき、計算量を大幅に減らすことができる。また、漸化式を解く際、等比数列に変形するための割り算で $p=0, 1$ の場合分けが発生することに注意し、最後に統合できるかを確認するとよい。