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

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

方針・初手

硬貨を投げる試行を、座標平面上の点の移動（ランダムウォーク）とみなして考える。原点 $(0,0)$ から出発し、表が出れば右上 $(1, 1)$ へ、裏が出れば右下 $(1, -1)$ へ移動するとする。このとき、$n$ 回投げ終わったときの座標は $(n, S_n)$ と表せる。硬貨を8回投げる全事象の数は $2^8 = 256$ 通りであり、各事象は同様に確からしいので、条件を満たす移動経路の数を数え上げて確率を求める。

解法1

(1)

$S_8 = 2$ となるのは、8回のうち表が5回、裏が3回出る場合である。全事象の数は $2^8 = 256$ 通りである。

条件「$S_n \neq 0$」は、1回目から8回目までのすべての $n$ において $S_n \neq 0$ であることを意味する。 $S_8 = 2 > 0$ であり、$S_n$ の値は1回の試行で1ずつしか変化しないため、途中で0にならないためには、すべての $n \ (1 \leqq n \leqq 8)$ において $S_n > 0$ でなければならない。特に1回目の結果は $S_1 > 0$ より、必ず表が出て $S_1 = 1$ となる。

したがって、点 $(1,1)$ から出発して、直線 $y=0$ （$x$ 軸）に一度も触れずに点 $(8,2)$ へ至る経路の数を求めればよい。

点 $(1,1)$ から点 $(8,2)$ へ至るすべての経路の数は、残りの7回の移動で右上に4回、右下に3回移動するので、

$$ {}_7\mathrm{C}_{4} = 35 \text{ (通り)} $$

である。このうち、直線 $y=0$ に触れる経路の数を引く。点 $(1,1)$ を直線 $y=0$ に関して対称移動した点は $(1,-1)$ である。点 $(1,1)$ から出発して $y=0$ 上の点 $P$ を経由し、点 $(8,2)$ に至る経路は、点 $(1,-1)$ から出発して同じ点 $P$ を経由し、点 $(8,2)$ に至る経路と1対1に対応する（鏡像の原理）。点 $(1,-1)$ と点 $(8,2)$ は直線 $y=0$ を挟んで反対側にあるため、点 $(1,-1)$ から点 $(8,2)$ へ至る経路は必ず直線 $y=0$ と交わる。よって、直線 $y=0$ に触れる経路の数は、点 $(1,-1)$ から点 $(8,2)$ へ至るすべての経路の数に等しい。点 $(1,-1)$ から点 $(8,2)$ へは $x$ 方向に $+7$、$y$ 方向に $+3$ 移動するため、右上に5回、右下に2回移動する経路であり、その数は、

$$ {}_7\mathrm{C}_{5} = 21 \text{ (通り)} $$

である。以上より、条件を満たす経路の数は

$$ 35 - 21 = 14 \text{ (通り)} $$

となる。求める確率は、

$$ \frac{14}{256} = \frac{7}{128} $$

である。

(2)

$S_4 = 0$ かつ $S_8 = 2$ となるのは、前半の4回で表が2回、裏が2回出て、後半の4回で表が3回、裏が1回出る場合である。

前半の4回で $S_4 = 0$ となる経路の数は、

$$ {}_4\mathrm{C}_{2} = 6 \text{ (通り)} $$

後半の4回で $S_8 - S_4 = 2$ となる経路の数は、

$$ {}_4\mathrm{C}_{3} = 4 \text{ (通り)} $$

したがって、条件を満たす経路の総数は、

$$ 6 \times 4 = 24 \text{ (通り)} $$

求める確率は、

$$ \frac{24}{2^8} = \frac{24}{256} = \frac{3}{32} $$

である。

解法2

（（1）の経路数を直接数え上げる方法）

$S_8 = 2$ かつすべての $n \ (1 \leqq n \leqq 8)$ で $S_n \neq 0$ となる条件は、$S_8 > 0$ より、常に $S_n > 0$ となることと同値である。各ステップ $n$ における $S_n = y$ となる経路の数を順に計算する。条件より $y \geqq 1$ の範囲のみを考える。

$n=1$: $S_1=1$ が $1$ 通り
$n=2$: $S_2=2$ が $1$ 通り
$n=3$: $S_3=1$ が $1$ 通り、$S_3=3$ が $1$ 通り
$n=4$: $S_4=2$ が $1+1=2$ 通り、$S_4=4$ が $1$ 通り
$n=5$: $S_5=1$ が $2$ 通り、$S_5=3$ が $2+1=3$ 通り、$S_5=5$ が $1$ 通り
$n=6$: $S_6=2$ が $2+3=5$ 通り、$S_6=4$ が $3+1=4$ 通り、$S_6=6$ が $1$ 通り
$n=7$: $S_7=1$ が $5$ 通り、$S_7=3$ が $5+4=9$ 通り、$S_7=5$ が $4+1=5$ 通り、$S_7=7$ が $1$ 通り
$n=8$: $S_8=2$ は $S_7=1$ または $S_7=3$ から遷移するため、$5+9=14$ 通り

よって、条件を満たす経路の数は $14$ 通りである。全事象の数は $2^8 = 256$ 通りであるから、求める確率は

$$ \frac{14}{256} = \frac{7}{128} $$

である。

解説

いわゆる「ランダムウォーク（酔歩）」に関する典型問題である。（1）は「鏡像の原理（反射の原理）」を用いることで鮮やかに解くことができる。特定の直線に触れない経路の数を、対称な点からの経路数に帰着させる手法は、カタラン数の導出などでも用いられる重要な考え方である。解法2のように、状態遷移を書き出して直接足し合わせる数え上げを行っても、8回程度であれば実用的な時間で正確に求めることができる。（2）は前半4回と後半4回で事象が独立していることに着目し、それぞれの確率（または場合の数）を掛け合わせるだけでよい基本問題である。