トップ› 東京大学› 2019年› 文系第3問

東京大学 2019年文系第3問解説

方針・初手

点Pの移動を数値化して扱うため、各頂点に座標を割り当てる。点Aを原点 $0$ とし、反時計回りを正の向きとして、Bを $1$、Cを $2$、…、Hを $7$（または $-1$）のように座標を設定する。 10回の操作で表が出る回数を $k$ とおき、10回後の点Pの座標を $k$ を用いて表すことで、事象Sが起こる条件を $k$ の方程式に帰着させる。

解法1

事象Sについて考える。点Aを座標 $0$ とし、反時計回りに隣接する頂点への移動を $+1$、時計回りに隣接する頂点への移動を $-1$ と表す。 10回の操作のうち、表が出た回数を $k$ （$0 \le k \le 10$）とすると、裏が出た回数は $10 - k$ である。 10回の操作後の点Pの座標 $X_{10}$ は、

$$ X_{10} = k \cdot 1 + (10 - k) \cdot (-1) = 2k - 10 $$

と表せる。事象S「点Pが点Aにある」が起こるのは、$X_{10}$ が $8$ の倍数となるときである。すなわち、$m$ を整数として、

$$ 2k - 10 = 8m $$

$$ k = 4m + 5 $$

と表されるときである。 $0 \le k \le 10$ を満たす整数 $m$ は $m = -1, 0, 1$ のいずれかであり、それぞれに対応する $k$ の値は $1, 5, 9$ である。

(1)

事象Sが起こるのは、表が $1$ 回、$5$ 回、$9$ 回出るいずれかの場合であり、これらは互いに排反である。それぞれの確率は反復試行の確率より以下のようになる。

・ $k=1$ のとき: $_{10}C_1 \left(\frac{1}{2}\right)^{10} = \frac{10}{1024}$ ・ $k=5$ のとき: $_{10}C_5 \left(\frac{1}{2}\right)^{10} = \frac{252}{1024}$ ・ $k=9$ のとき: $_{10}C_9 \left(\frac{1}{2}\right)^{10} = \frac{10}{1024}$

よって、事象Sが起こる確率は、

$$ \frac{10 + 252 + 10}{1024} = \frac{272}{1024} = \frac{17}{64} $$

(2)

事象Sと事象T（途中で少なくとも1回点Fに移動する）がともに起こる確率を求める。点Fは点Aから反時計回りに $5$、時計回りに $3$ の位置にあるため、移動の過程での座標 $X_i$ （$1 \le i \le 10$）が $X_i \equiv 5 \pmod 8$ となることが事象Tの条件である。 (1)で求めた $k=1, 5, 9$ のそれぞれの場合について、事象Tを満たす経路の数を調べる。

(i)

$k=1$ のとき

表が $1$ 回、裏が $9$ 回であり、$X_{10} = -8$ である。移動中に最も正の方向に進んでも座標は $1$ であり、最終的に $-8$ に到達するためには、途中で必ず座標 $-3$ （点F）を通過する。したがって、この場合の $_{10}C_1 = 10$ 通りの経路はすべて事象Tを満たす。

(ii)

$k=9$ のとき

表が $9$ 回、裏が $1$ 回であり、$X_{10} = 8$ である。移動中に最も負の方向に進んでも座標は $-1$ であり、最終的に $8$ に到達するためには、途中で必ず座標 $5$ （点F）を通過する。したがって、この場合の $_{10}C_9 = 10$ 通りの経路はすべて事象Tを満たす。

(iii)

$k=5$ のとき

表が $5$ 回、裏が $5$ 回であり、$X_{10} = 0$ である。経路の総数は $_{10}C_5 = 252$ 通りである。このうち、途中で一度も点Fを通過しない経路の数を求める。点Fを通過しない条件は、すべての $i$ （$1 \le i \le 10$）において $X_i \neq 5$ かつ $X_i \neq -3$ が成り立つことである。これの余事象として、「$X_i = 5$ に到達する」または「$X_i = -3$ に到達する」経路の数を折り返しの原理（鏡像法）を用いて求める。

・ $X_i = 5$ に到達する経路の数初めて $X_i = 5$ となった時点でそれ以降の移動の正負を反転させると、本来の終点 $0$ が $5 + 5 = 10$ に移る経路と1対1に対応する。 10回の移動で座標 $10$ に到達するのは表が $10$ 回のときの $_{10}C_{10} = 1$ 通りである。

・ $X_i = -3$ に到達する経路の数初めて $X_i = -3$ となった時点で反転させると、本来の終点 $0$ が $-3 - 3 = -6$ に移る経路と1対1に対応する。 10回の移動で座標 $-6$ に到達するのは表が $2$ 回、裏が $8$ 回のときの $_{10}C_2 = 45$ 通りである。

・重複の確認 $X_i = 5$ と $X_i = -3$ の両方に到達するには、少なくとも一方から他方への移動距離 $8$ が必要である。仮に $0 \to 5 \to -3$ と移動する場合、最短でも $5 + 8 = 13$ 回の移動が必要であり、10回では不可能である。逆の順序も同様に $3 + 8 = 11$ 回必要であり不可能。よって重複はない。

したがって、点Fを少なくとも1回通過する経路の数は $1 + 45 = 46$ 通りである。

以上より、事象Sと事象Tがともに起こる経路の総数は、

$$ 10 + 10 + 46 = 66 $$

通りである。すべての移動の仕方は $2^{10} = 1024$ 通りなので、求める確率は

$$ \frac{66}{1024} = \frac{33}{512} $$

解法2

(2)の（iii） $k=5$ の場合において、事象Tを満たす経路数を数え上げる別解を示す。

点Aを座標 $0$ とし、点Fを座標 $5$ または $-3$ と考える。点Fを一度も通過せずに10回の操作後に座標 $0$ に戻る経路の数を直接求める。 $i$ 回目の操作後に座標 $x$ に到達する経路の数を $N(i, x)$ とする。 1回の操作で座標は $\pm 1$ 変化するため、

$$ N(i, x) = N(i-1, x-1) + N(i-1, x+1) $$

が成り立つ。ただし、点F（$x = 5$ または $x = -3$）に到達した場合はそこから先の移動を考えないため、$N(i, 5) = 0$、$N(i, -3) = 0$ として計算する。初期状態は $N(0, 0) = 1$、それ以外の $x$ については $N(0, x) = 0$ である。この規則に従って $i=10$ まで順に経路数を計算すると、以下の表のようになる。

$i$	$x=-2$	$x=-1$	$x=0$	$x=1$	$x=2$	$x=3$	$x=4$
$0$	$0$	$0$	$1$	$0$	$0$	$0$	$0$
$1$	$0$	$1$	$0$	$1$	$0$	$0$	$0$
$2$	$1$	$0$	$2$	$0$	$1$	$0$	$0$
$3$	$0$	$3$	$0$	$3$	$0$	$1$	$0$
$4$	$3$	$0$	$6$	$0$	$4$	$0$	$1$
$5$	$0$	$9$	$0$	$10$	$0$	$5$	$0$
$6$	$9$	$0$	$19$	$0$	$15$	$0$	$5$
$7$	$0$	$28$	$0$	$34$	$0$	$20$	$0$
$8$	$28$	$0$	$62$	$0$	$54$	$0$	$20$
$9$	$0$	$90$	$0$	$116$	$0$	$74$	$0$
$10$	$90$	$0$	$206$	$0$	$190$	$0$	$74$

表より、10回後に点Fを通過せずに座標 $0$ に戻る経路の数は $N(10, 0) = 206$ 通りである。 $k=5$ となる経路の総数は $_{10}C_5 = 252$ 通りであるから、点Fを少なくとも1回通過する経路の数は

$$ 252 - 206 = 46 $$

通りとなる。（以下、解法1と同様）

解説

ランダムウォーク（点が確率的に移動する問題）の典型問題である。 (1)は各頂点に適切に座標を設定し、移動を数値化することで、二項分布の基本的な計算に帰着できる。 (2)の「途中で特定の点を通過する（あるいは通過しない）確率」を求める手法としては、解法1で用いた「折り返しの原理（鏡像法）」と、解法2で用いた「漸化式（推移表）による数え上げ」の2つのアプローチが標準的である。折り返しの原理は計算量が少なくエレガントな解法だが、特定の条件（吸収壁が1つ、あるいは互いに干渉しない）を満たす必要がある。本問では両側の吸収壁に同時に到達することが不可能であるため、シンプルな足し引きで計算できる。一方、漸化式を用いた表による数え上げは、多少の計算の手間はかかるものの、条件が複雑になっても機械的に答えを確認しやすく、試験会場でも使いやすい方法である。