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

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

方針・初手

ゲームのルールより、石は常に水平右側または垂直下側にしか移動しないため、元の位置に戻ったり、左や上に移動したりすることはありません。また、操作のたびに選んだ数字を丸で囲むため、「ゲームの終了時に数字 $j$ が丸で囲まれている」事象は、「ゲームの最初、または途中で石がマス $j$ に置かれる」事象と同値です。

各マス $i$ から1回の操作で移動できるマスの集合を $N(i)$、その要素数を $|N(i)|$ とします。マス $i$ に石があるとき、次に選ばれるマスは集合 $N(i)$ の中から等確率で選ばれるため、特定のマスへの遷移確率は $\frac{1}{|N(i)|}$ です。マス $j$ に石が置かれるのは、 (i) 最初の操作 (a) でマス $j$ が選ばれる（確率 $\frac{1}{12}$） (ii) 他のマス $i$ に石が置かれ、そこから1手でマス $j$ に移動するのいずれかであり、各経路は互いに排反です。したがって、マス $j$ が丸で囲まれる確率 $p_j$ は、次の漸化式で表すことができます。

$$ p_j = \frac{1}{12} + \sum_{i} p_i \cdot \frac{1}{|N(i)|} $$

ただし、和 $\sum$ は「マス $i$ からマス $j$ へ移動可能である（すなわち $j \in N(i)$）」ようなすべてのマス $i$ について取ります。この式を用いて、数字の小さいマスから順に確率を求めていきます。

解法1

図の配置から、各マス $i$ において移動可能なマスの個数 $|N(i)|$ を調べます。

マス1: 2, 3, 4, 5, 6, 10, 12 の 7個 $\to |N(1)| = 7$
マス2: 3, 4, 5, 7, 11 の 5個 $\to |N(2)| = 5$
マス3: 4, 5, 8 の 3個 $\to |N(3)| = 3$
マス4: 5, 9 の 2個 $\to |N(4)| = 2$
マス6: 7, 8, 9, 10, 12 の 5個 $\to |N(6)| = 5$
マス7: 8, 9, 11 の 3個 $\to |N(7)| = 3$
マス10: 11, 12 の 2個 $\to |N(10)| = 2$

(1) マス2へ1手で移動できるのはマス1からのみです。したがって、$p_2$ は以下の式で求められます。

$$ p_2 = \frac{1}{12} + p_1 \cdot \frac{1}{|N(1)|} $$

マス1へ移動してくるマスはないため、$p_1 = \frac{1}{12}$ です。これと $|N(1)| = 7$ を代入します。

$$ p_2 = \frac{1}{12} + \frac{1}{12} \cdot \frac{1}{7} = \frac{1}{12} \left( 1 + \frac{1}{7} \right) = \frac{1}{12} \cdot \frac{8}{7} = \frac{2}{21} $$

(2) 第1行にあるマス 1, 2, 3, 4, 5 について考えます。石は右または下にしか移動しないため、他の行から第1行のマスへ移動してくることはありません。したがって、第1行のマス $k+1$ （$k=1, 2, 3, 4$）に到達するのは、最初からそこに置かれるか、同じ行の左側にあるマス $1, 2, \dots, k$ のいずれかから移動してくる場合のみです。これを数式で表すと、

$$ p_{k+1} = \frac{1}{12} + \sum_{i=1}^{k} \frac{p_i}{|N(i)|} $$

となります。ここで、一つ前のマス $k$ における確率の式

$$ p_k = \frac{1}{12} + \sum_{i=1}^{k-1} \frac{p_i}{|N(i)|} $$

を用いると、$p_{k+1}$ は次のように変形できます。

$$ p_{k+1} = \left( \frac{1}{12} + \sum_{i=1}^{k-1} \frac{p_i}{|N(i)|} \right) + \frac{p_k}{|N(k)|} = p_k + \frac{p_k}{|N(k)|} = p_k \left( 1 + \frac{1}{|N(k)|} \right) $$

この関係式を用いて、順に計算します。

$$ p_3 = p_2 \left( 1 + \frac{1}{|N(2)|} \right) = \frac{2}{21} \left( 1 + \frac{1}{5} \right) = \frac{2}{21} \cdot \frac{6}{5} = \frac{4}{35} $$

$$ p_4 = p_3 \left( 1 + \frac{1}{|N(3)|} \right) = \frac{4}{35} \left( 1 + \frac{1}{3} \right) = \frac{4}{35} \cdot \frac{4}{3} = \frac{16}{105} $$

$$ p_5 = p_4 \left( 1 + \frac{1}{|N(4)|} \right) = \frac{16}{105} \left( 1 + \frac{1}{2} \right) = \frac{16}{105} \cdot \frac{3}{2} = \frac{8}{35} $$

(3) マス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_6, p_7, p_{10}$ を順に求めます。まず、第1列（マス 1, 6, 10, 12）についても、他の列から移動してくることはないため、(2)と同様の漸化式が成り立ちます。

$$ p_6 = p_1 \left( 1 + \frac{1}{|N(1)|} \right) = \frac{1}{12} \left( 1 + \frac{1}{7} \right) = \frac{2}{21} $$

$$ p_{10} = p_6 \left( 1 + \frac{1}{|N(6)|} \right) = \frac{2}{21} \left( 1 + \frac{1}{5} \right) = \frac{2}{21} \cdot \frac{6}{5} = \frac{4}{35} $$

次に $p_7$ を求めます。マス7へ移動できるのはマス2とマス6です。

$$ p_7 = \frac{1}{12} + \frac{p_2}{|N(2)|} + \frac{p_6}{|N(6)|} $$

ここに $p_2 = \frac{2}{21}$、$p_6 = \frac{2}{21}$、$|N(2)| = 5$、$|N(6)| = 5$ を代入します。

$$ p_7 = \frac{1}{12} + \frac{2/21}{5} + \frac{2/21}{5} = \frac{1}{12} + \frac{4}{105} = \frac{35}{420} + \frac{16}{420} = \frac{51}{420} = \frac{17}{140} $$

最後に、$p_{11}$ を計算します。

$$ \begin{aligned} p_{11} &= \frac{1}{12} + \frac{p_2}{5} + \frac{p_7}{3} + \frac{p_{10}}{2} \\ &= \frac{1}{12} + \frac{2/21}{5} + \frac{17/140}{3} + \frac{4/35}{2} \\ &= \frac{1}{12} + \frac{2}{105} + \frac{17}{420} + \frac{2}{35} \end{aligned} $$

分母を 420 に揃えて通分します。

$$ \begin{aligned} p_{11} &= \frac{35}{420} + \frac{8}{420} + \frac{17}{420} + \frac{24}{420} \\ &= \frac{84}{420} \\ &= \frac{1}{5} \end{aligned} $$

解説

状態遷移（マルコフ連鎖）に関する確率の問題です。移動が一方向（右または下）に限定されているため、経路のトポロジカルソート（到達順序の整理）が可能であり、上流のマスから順に到達確率を確定させていく動的計画法的なアプローチが非常に有効です。

特に (2) において、同じ行（または列）だけで遷移が完結する場合、シグマ記号で表された確率の総和が「直前の確率 $p_k$」を用いて $p_{k+1} = p_k \left( 1 + \frac{1}{|N(k)|} \right)$ と簡略化できることに気付けると、計算量を劇的に減らし、計算ミスを防ぐことができます。