トップ› 京都大学› 2016年› 理系第5問

京都大学 2016年理系第5問解説

方針・初手

点の数が 6 個ありますが、図の対称性と移動のルールに着目すると、動点 X の $y$ 座標は確率の計算に影響を与えず、$x$ 座標が 0, 1, 2 のいずれであるかだけで状態を分類できることに気づくのが最大のポイントです。
$n$ 秒後の $x$ 座標が 0, 1, 2 である確率をそれぞれ $p_n,\ q_n,\ r_n$ とおき、推移確率を考えて連立漸化式を立てます。
$x = 1$ に関する対称性から $p_n - r_n$ の関係式を導き、$p_n + q_n + r_n = 1$ と組み合わせて $p_n$ だけの隣接 2 項間漸化式に帰着させます。

解法1

$n$ 秒後に動点 X の $x$ 座標が 0, 1, 2 である確率をそれぞれ $p_n,\ q_n,\ r_n$ とする。

時刻 0 では点 $(0,\ 0)$ にいるため、$p_0 = 1,\ q_0 = 0,\ r_0 = 0$ である。

各状態からの遷移について調べる。

$x = 0$ の点にいる場合：そこから出る辺は 2 本あり、移動先は $x = 0$ の点が 1 個、$x = 1$ の点が 1 個である。したがって、確率 $\dfrac{1}{2}$ で $x = 0$ に留まり、確率 $\dfrac{1}{2}$ で $x = 1$ に移動する。
$x = 1$ の点にいる場合：そこから出る辺は 3 本あり、移動先は $x = 0,\ 1,\ 2$ の点が各 1 個である。したがって、確率 $\dfrac{1}{3}$ ずつで $x = 0,\ 1,\ 2$ のいずれかに移動する。
$x = 2$ の点にいる場合：$x = 0$ の場合と対称であり、確率 $\dfrac{1}{2}$ で $x = 2$ に留まり、確率 $\dfrac{1}{2}$ で $x = 1$ に移動する。

これより、次の連立漸化式が成り立つ。

$$ p_{n+1} = \frac{1}{2}p_n + \frac{1}{3}q_n \quad \cdots (1) $$

$$ q_{n+1} = \frac{1}{2}p_n + \frac{1}{3}q_n + \frac{1}{2}r_n \quad \cdots (2) $$

$$ r_{n+1} = \frac{1}{3}q_n + \frac{1}{2}r_n \quad \cdots (3) $$

$(1) - (3)$ より、

$$ p_{n+1} - r_{n+1} = \frac{1}{2}p_n - \frac{1}{2}r_n = \frac{1}{2}(p_n - r_n) $$

数列 $\{p_n - r_n\}$ は初項 $p_0 - r_0 = 1$、公比 $\dfrac{1}{2}$ の等比数列であるから、

$$ p_n - r_n = \left(\frac{1}{2}\right)^n \quad \cdots (4) $$

また、動点 X は常にいずれかの点に存在するため、

$$ p_n + q_n + r_n = 1 \quad \cdots (5) $$

$(4)$ より $r_n = p_n - \left(\dfrac{1}{2}\right)^n$ であるから、$(5)$ に代入すると、

$$ q_n = 1 - p_n - r_n = 1 - 2p_n + \left(\frac{1}{2}\right)^n $$

これを $(1)$ に代入すると、

$$ p_{n+1} = \frac{1}{2}p_n + \frac{1}{3}\!\left(1 - 2p_n + \left(\frac{1}{2}\right)^n\right) = -\frac{1}{6}p_n + \frac{1}{3} + \frac{1}{3}\left(\frac{1}{2}\right)^n \quad \cdots (6) $$

この漸化式を変形するために、定数 $A,\ B$ を用いて

$$ p_{n+1} - A\!\left(\frac{1}{2}\right)^{n+1} - B = -\frac{1}{6}\!\left(p_n - A\!\left(\frac{1}{2}\right)^n - B\right) $$

と表せると仮定する。右辺を展開して整理すると、

$$ p_{n+1} = -\frac{1}{6}p_n + \frac{2}{3}A\!\left(\frac{1}{2}\right)^n + \frac{7}{6}B $$

$(6)$ と係数を比較して、

$$ \frac{2}{3}A = \frac{1}{3} \implies A = \frac{1}{2}, \qquad \frac{7}{6}B = \frac{1}{3} \implies B = \frac{2}{7} $$

よって、漸化式は次のように変形できる。

$$ p_{n+1} - \left(\frac{1}{2}\right)^{n+2} - \frac{2}{7} = -\frac{1}{6}\!\left(p_n - \left(\frac{1}{2}\right)^{n+1} - \frac{2}{7}\right) $$

これは、数列 $\left\{p_n - \left(\dfrac{1}{2}\right)^{n+1} - \dfrac{2}{7}\right\}$ が公比 $-\dfrac{1}{6}$ の等比数列であることを示している。

初項は $p_0 - \dfrac{1}{2} - \dfrac{2}{7} = 1 - \dfrac{7}{14} - \dfrac{4}{14} = \dfrac{3}{14}$ であるから、

$$ p_n - \left(\frac{1}{2}\right)^{n+1} - \frac{2}{7} = \frac{3}{14}\left(-\frac{1}{6}\right)^n $$

したがって、

$$ p_n = \frac{3}{14}\left(-\frac{1}{6}\right)^n + \left(\frac{1}{2}\right)^{n+1} + \frac{2}{7} $$

解説

複雑に見えるランダムウォーク（点の移動）の問題ですが、$y$ 座標に関する移動の対称性により、実質的には 3 つの状態間を行き来する問題に還元できます。状態を適切にまとめることが計算量削減の第一歩です。

3 元連立漸化式においては、「確率の和が 1」という条件と、「対称性による差分（今回は $p_n - r_n$）」を用いるのが定石です。これにより、式を 1 つの変数の漸化式に絞り込むことができます。

導出された $p_{n+1} = -\dfrac{1}{6}p_n + \dfrac{1}{3}\left(\dfrac{1}{2}\right)^n + \dfrac{1}{3}$ 型の漸化式は、特解 $A\!\left(\dfrac{1}{2}\right)^n + B$ を置いて係数比較で変形するのが、最も見通しが良く論理の飛躍もない処理方法です。