京都大学 2004年 理系 第6問 解説

方針・初手

操作は $k=1, 2, \dots, N, N+1$ の順に行われる。$k=1 \dots N$ までの操作と、最後の $k=N+1$ の操作は、箱 $N+1$（赤玉の初期位置）の扱われ方が異なるため、分けて考える。「これから操作の主体となる箱（未操作の箱）には、絶対に赤玉が入っていない」という重要な性質を見抜くことがポイントである。

解法1

$k$ 回目の操作が終了した直後に、赤玉が箱 $i$（$1 \leqq i \leqq N+1$）に入っている確率を $P_k(i)$ とする。初期状態（$k=0$）では $P_0(N+1) = 1$、$P_0(i) = 0$（$1 \leqq i \leqq N$）である。

「未操作の箱には赤玉が入らない」の証明：

$k-1$ 回目の操作直後において、箱 $k, k+1, \dots, N$ には赤玉が入っていないこと（$P_{k-1}(j) = 0$、$k \leqq j \leqq N$）を帰納的に示す。

$k=1$ のとき、初期状態より成立する。ある $m$ 回目において成立すると仮定する。$m$ 回目の操作では、箱 $m$（赤玉なし）と他の箱を交換するため、未操作の箱 $j > m$ に移動するのは必ず白玉である。よって $m$ 回目の操作直後も箱 $m+1, \dots, N$ に赤玉は入らない。

$k \leqq N$ における漸化式：

$k$ 回目の操作後に赤玉が箱 $N+1$ にあるのは：

• 操作前に赤玉が箱 $N+1$ にあり、交換相手として箱 $N+1$ 以外が選ばれる（確率 $\dfrac{N-1}{N}$）
• 操作前に赤玉が箱 $k$ にあり、交換相手として箱 $N+1$ が選ばれる（確率 $\dfrac{1}{N}$）

の2つの場合のみである。よって

$$ P_k(N+1) = P_{k-1}(N+1) \times \frac{N-1}{N} + P_{k-1}(k) \times \frac{1}{N} $$

ここで $P_{k-1}(k) = 0$ であるから、

$$ P_k(N+1) = \frac{N-1}{N} P_{k-1}(N+1) $$

これは公比 $\dfrac{N-1}{N}$ の等比数列であり、$P_0(N+1) = 1$ より

$$ P_N(N+1) = \left( \frac{N-1}{N} \right)^N $$

$k = N+1$ 回目の操作：

この操作では箱 $N+1$ と箱 $1 \sim N$ のいずれかを交換する。操作直前に赤玉が箱 $N+1$ にある場合（確率 $P_N(N+1)$）、赤玉は必ず箱 $N+1$ から出ていく。操作直前に赤玉が箱 $N+1$ 以外にある場合（確率 $1 - P_N(N+1)$）、赤玉が入っている箱が選ばれれば（確率 $\dfrac{1}{N}$）赤玉は箱 $N+1$ に移動する。

したがって、

$$\begin{aligned} P_{N+1}(N+1) &= P_N(N+1) \times 0 + \{ 1 - P_N(N+1) \} \times \frac{1}{N} \\ &= \frac{1}{N} \left\{ 1 - \left( \frac{N-1}{N} \right)^N \right\} \end{aligned}$$

解説

確率の漸化式と状態遷移を考える問題であるが、「赤玉がどのように移動し得るか」を絞り込むことが最大の鍵となる。

「未操作の箱には絶対に赤玉が入っていない」という事実に気づけば、$k$ 回目の操作前に箱 $k$ に赤玉が入っている確率が $0$ であることが分かり、状態遷移が劇的にシンプルになる。$1$ 回目から $N$ 回目までは、赤玉は箱 $N+1$ から出ていく一方であり、最後の $N+1$ 回目の操作だけが外に出ていた赤玉を確率 $\dfrac{1}{N}$ で引き戻す、という構造になっている。

答え

$$ \frac{1}{N} \left\{ 1 - \left( \frac{N-1}{N} \right)^N \right\} $$