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

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

方針・初手

各マスに石が置かれる確率を、それより前のマスに石が置かれる確率を用いて順次求めていく。ゲームのルールより、マス $k$ に石が置かれたとき、そこから移動できるマス（水平右側または垂直下側）の個数を $n_k$ とすると、次にいずれかのマスへ移動する確率は等しく $\frac{1}{n_k}$ となる。また、最初にどのマスが選ばれる確率も等しく $\frac{1}{12}$ である。したがって、あるマス $j$ に石が置かれる（丸で囲まれる）確率 $p_j$ は、初手でマス $j$ が選ばれる確率 $\frac{1}{12}$ と、他のマス $k$ からマス $j$ へ遷移してくる確率 $\frac{p_k}{n_k}$ の総和で表される。マス $j$ へ直接移動できるマスの集合を $S_j$ とすると、以下の漸化式が成り立つ。

$$ p_j = \frac{1}{12} + \sum_{k \in S_j} \frac{p_k}{n_k} $$

この関係を用いて、左上のマスから順に確率を計算していく。

解法1

(1)

図の配置より、各マスから移動できるマスの個数 $n_k$ は以下のようになる。 $n_1 = 7, n_2 = 5, n_3 = 3, n_4 = 2$ $n_6 = 5, n_7 = 3, n_8 = 1$ $n_{10} = 2$ （終了条件であるマス $5, 9, 11, 12$ からは移動しない）

初手でマス $1$ に置かれる確率は $p_1 = \frac{1}{12}$ である。マス $2$ へ直接移動できるのはマス $1$ のみ（$S_2 = \{1\}$）であるから、

$$ p_2 = \frac{1}{12} + \frac{p_1}{n_1} = \frac{1}{12} + \frac{1}{12} \times \frac{1}{7} = \frac{2}{21} $$

(2)

方針で立てた式を用いて、順次確率を求める。マス $3$ へ移動できるのはマス $1, 2$（$S_3 = \{1, 2\}$）であり、$p_2 = \frac{1}{12} + \frac{p_1}{n_1}$ であることを利用すると、計算を簡略化できる。

$$ p_3 = \frac{1}{12} + \frac{p_1}{n_1} + \frac{p_2}{n_2} = p_2 + \frac{p_2}{n_2} = \frac{2}{21} + \frac{2}{21} \times \frac{1}{5} = \frac{2}{21} \times \frac{6}{5} = \frac{4}{35} $$

同様の構造を利用して、$p_4, p_5$ を順に計算する。

$$ p_4 = p_3 + \frac{p_3}{n_3} = \frac{4}{35} + \frac{4}{35} \times \frac{1}{3} = \frac{4}{35} \times \frac{4}{3} = \frac{16}{105} $$

$$ p_5 = p_4 + \frac{p_4}{n_4} = \frac{16}{105} + \frac{16}{105} \times \frac{1}{2} = \frac{16}{105} \times \frac{3}{2} = \frac{8}{35} $$

次に、$p_{11}$ を求めるために必要な $p_6, p_7, p_{10}$ を計算する。

$$ p_6 = \frac{1}{12} + \frac{p_1}{n_1} = \frac{1}{12} + \frac{1}{12} \times \frac{1}{7} = \frac{2}{21} $$

マス $10$ へ移動できるのはマス $1, 6$ であり、$p_6 = \frac{1}{12} + \frac{p_1}{n_1}$ を利用すると、

$$ p_{10} = \frac{1}{12} + \frac{p_1}{n_1} + \frac{p_6}{n_6} = p_6 + \frac{p_6}{n_6} = \frac{2}{21} \times \frac{6}{5} = \frac{4}{35} $$

マス $7$ へ移動できるのはマス $2, 6$ であるから、

$$ p_7 = \frac{1}{12} + \frac{p_2}{n_2} + \frac{p_6}{n_6} = \frac{1}{12} + \frac{2}{21} \times \frac{1}{5} + \frac{2}{21} \times \frac{1}{5} = \frac{1}{12} + \frac{4}{105} = \frac{17}{140} $$

マス $11$ へ移動できるのはマス $2, 7, 10$ であるから、求めた値を用いて $p_{11}$ を計算する。

$$ p_{11} = \frac{1}{12} + \frac{p_2}{n_2} + \frac{p_7}{n_7} + \frac{p_{10}}{n_{10}} $$

$$ p_{11} = \frac{1}{12} + \frac{2}{105} + \frac{17}{140} \times \frac{1}{3} + \frac{4}{35} \times \frac{1}{2} = \frac{35}{420} + \frac{8}{420} + \frac{17}{420} + \frac{24}{420} = \frac{84}{420} = \frac{1}{5} $$

(3)

まず $p_{12}$ を求める。マス $12$ へ移動できるのはマス $1, 6, 10$ であり、$p_{10} = \frac{1}{12} + \frac{p_1}{n_1} + \frac{p_6}{n_6}$ を利用すると、

$$ p_{12} = p_{10} + \frac{p_{10}}{n_{10}} = \frac{4}{35} \times \frac{3}{2} = \frac{6}{35} $$

次に $p_9$ を求める。ゲームは各操作で必ず水平右側または垂直下側へ移動するため、無限に続くことはなく、必ず終了条件であるマス $5, 9, 11, 12$ のいずれかに到達して終了する。したがって、これら4つのマスでゲームが終了する事象は互いに排反であり、最終的に到達する確率の和は $1$ となる。

$$ p_5 + p_9 + p_{11} + p_{12} = 1 $$

この関係を用いると、$p_9$ は以下のように求められる。

$$ p_9 = 1 - (p_5 + p_{11} + p_{12}) = 1 - \left( \frac{8}{35} + \frac{1}{5} + \frac{6}{35} \right) = 1 - \frac{21}{35} = 1 - \frac{3}{5} = \frac{2}{5} $$

確率の大小を比較するため、求めた4つの値を分母 $35$ で揃える。

$$ p_5 = \frac{8}{35}, \quad p_9 = \frac{14}{35}, \quad p_{11} = \frac{7}{35}, \quad p_{12} = \frac{6}{35} $$

以上より、最も大きいものは $p_9$ であり、その値は $\frac{2}{5}$ である。

解説

グラフ上のランダムウォーク（確率過程）を題材にした問題である。移動先が常に右側か下側であり、後戻りしないという性質から、動的計画法のように「移動元のマスの確率を用いて移動先の確率を求める」漸化式を立てるのが定石となる。 (2)や(3)の計算において、共通する移動経路をまとめて $p_{k} = p_{k-1} + \frac{p_{k-1}}{n_{k-1}}$ のように置き換える工夫に気付くと、計算量を劇的に減らすことができる。また(3)では、ゲームが必ずいずれかの終了マスで終わることに着目し、確率の総和が1になる性質（全確率の法則）を利用すると、経路が複雑な $p_9$ の直接計算を回避でき、計算ミスのリスクを抑えることができる。