入試数学コンテスト第2回第6問解答解説

$n$ 人の乗客がいるときに，$n$ 人目が正しい席に座る確率 $p_n$ とおく．考えている事象を以下のように排反に場合分けする．

• $1$ 人目が席 $1$ に座るとき

このときは全員が正しい席に座れるから，$n$ 人目が正しい席に座る確率は $\frac{1}{n} \cdot 1$ である．

• $1$ 人目が席 $i$（$1 < i < n$）に座るとき

このときは，$2$ 〜 $i-1$ 人目までが正しい席に座り，$i$ 人目が残った席 $$1, i+1, i+2, \dots, n$$ の中からランダムに座ることになる．これは，（席 $i$ が席 $1$ に置き換わっているという点を除けば）$i$ 人目から $n$ 人目までの $n-i+1$ 人で問題文のやり方で飛行機に乗る状況と同じである．しかも，$n$ 人目の人から見ると，席 $i$ が席 $1$ に置き換わっていることは「自分の席に座れる確率」を計算する上で影響がない．（$\because$ $i \neq n$ なので．）

よってこの場合， $n$ 人目が正しい席に座る確率は $\frac{1}{n} \cdot p_{n - i + 1}$ である．

• $1$ 人目が席 $n$ に座るとき

この場合，$n$ 人目が正しい席に座る確率は $\frac{1}{n} \cdot 0$ である．

以上を合わせると，$p_n$ は

$$p_n = \frac{1}{n} + \sum_{i = 2}^{n-1} \frac{1}{n} \cdot p_{n-i+1} \hspace{10pt}(n \geq 2)$$

を満たす．漸化式の $\sum$ において $j = n-i+1$ とおいて分母を払うと，

$$n p_n = 1 + \sum_{j=2}^{n-1}p_j\hspace{10pt}(n \geq 2)$$

となる．$n$ を $n + 1$ で置き換えると

$$(n+1) p_{n+1} = 1 + \sum_{j=2}^{n}p_j\hspace{10pt}(n + 1 \geq 2)$$

となるから，これらの式を引き算すると

$$(n+1) p_{n+1} - n p_n = p_n \hspace{10pt}(n \geq 2)$$

となり，結局

$$p_{n+1} = p_n \hspace{10pt}(n \geq 2)$$

となる．これと

$$p_2 = \frac{1}{2}$$

より $n \geq 2$ に対し $p_n = \frac{1}{2}$ だから，特に $p_{100} = \frac{1}{2}$ である．

$4$ 人目が自分の席に座れない確率を $q$ として，これを計算する．あり得る場合を $1$ 人目が座る席で場合分けして考える．

• $1$ 人目が席 $1$ or $5$ 〜 $200$ に座るとき

この場合 $2$，$3$，$4$ 人目は自分の席に座れる．

• $1$ 人目が席 $2$ に座るとき

$2$ 人目が席 $1$ or $5$ 〜 $200$ に座ると $3$，$4$ 人目は自分の席に座れる．

$2$ 人目が席 $3$ に座るとき，$3$ 人目は席 $1, 4, 5, \dots 200$ の中から選ぶ．よって $4$ 人目が自分の席に座れない確率は $\frac{1}{200} \cdot \frac{1}{199} \cdot \frac{1}{198}$ となる．

$2$ 人目が席 $4$ に座るとき， $4$ 人目は自分の席に座れない．この確率は $\frac{1}{200} \cdot \frac{1}{199}$ である．

• $1$ 人目が席 $3$ に座るとき

$2$ 人目は自分の席に座れる．$3$ 人目は席 $1, 4, 5, \dots 200$ の中から選ぶ．よって $4$ 人目が自分の席に座れない確率は $\frac{1}{200} \cdot \frac{1}{198}$ となる．

• $1$ 人目が席 $4$ に座るとき

$4$ 人目は自分の席に座れない．この確率は $\frac{1}{200}$ である．

以上を全て足し合わせると，

$$\begin{aligned} q &= \frac{1}{200} \cdot \frac{1}{199} \cdot \frac{1}{198} + \frac{1}{200} \cdot \frac{1}{199} + \frac{1}{200} \cdot \frac{1}{198} + \frac{1}{200} \\ &= \frac{1}{200} \left(\frac{1}{199} \cdot \frac{1}{198} + \frac{1}{199} + \frac{1}{198} + 1\right) \\ &= \frac{1}{200}\left(\frac{1}{199} + 1\right)\left(\frac{1}{198} + 1\right) \\ &= \frac{1}{200} \cdot \frac{200}{199} \cdot \frac{199}{198} \\ &= \frac{1}{198} \end{aligned}$$

だから，求める値は $1 - q = \frac{197}{198}$ である．

$4$ 人目が自分の席に座れない確率を $q$ として，これを計算する．あり得る場合を席 $4$ に誰が座るかで場合分けして考える．

• $1$ 人目が座る場合

この確率は $\frac{1}{200}$ である．

• $2$ 人目が座る場合

この確率は，$1$ 人目が席 $2$ を選んで $2$ 人目が席 $4$ を選ぶ確率だから，$\frac{1}{200} \cdot \frac{1}{199}$ である．

• $3$ 人目が座る場合

この確率は，「$1$ 人目が席 $3$ に座る」or「$1$ 人目が席 $2$ に座り，$2$ 人目が席 $3$ に座る」のどちらかが起こった上で $3$ 人目が席 $4$ を選ぶ確率だから，$\left(\frac{1}{200} + \frac{1}{200} \cdot \frac{1}{199} \right) \cdot \frac{1}{198}$ である．

以上を足し合わせて， $$\begin{aligned} q &= \frac{1}{200} + \frac{1}{200} \cdot \frac{1}{199} + \left(\frac{1}{200} + \frac{1}{200} \cdot \frac{1}{199} \right) \cdot \frac{1}{198}\\ &=\frac{1}{198} \end{aligned}$$ となる．

よって求める値は $1 - q = \frac{197}{198}$ である．

$2 \leq k \leq n$ とし，$k$ 人目が席 $k$ に座れない確率を $q_k$ とする．この事象を席 $k$ に誰が座るかで場合分けして考える．

席 $k$ に $j$ 人目（$1 \leq j \leq k-1$）が座るとする．

• $j = 1$ のとき

$1$ 番目の人は $n$ 個の座席から等確率でひとつを選ぶから，そのときに席 $k$ が選ばれる確率は $\frac{1}{n}$ である．

• $j > 1$ のとき

$j$ 人目が席 $k$ に座る確率は，席 $j$ が空いておらず，かつ残った $n - (j - 1)$ 個の席の中から席 $k$ が選ばれる確率である．

まず，$j$ 人目の番で席 $j$ が空いていない確率は $q_j$ である．すると残った $n - (j - 1)$ 個の席の中に席 $k$ があるかどうかが問題となるが，実は後で示すように，$j$ 人目の番で席 $j$ が空いていないとき，残った $n - (j - 1)$ 個の席は席 $1, j+1, j+2, \dots, n$ である．（すると $j < k$ だから席 $k$ は残っている．）

よって $j$ 人目が席 $k$ に座る確率は

$$q_j \cdot \frac{1}{n - (j - 1)}$$ である．

以上より，$2 \leq k \leq n$ のとき

$$q_k = \frac{1}{n} + \sum_{j = 2}^{k - 1} q_j \cdot \frac{1}{n - j + 1}$$

が成り立つ．右辺の $\sum$ を $2 \leq j < k - 1$ と $j = k - 1$ に分解することで，$k > 2$ のとき

$$\begin{aligned} q_k &= \frac{1}{n} + \sum_{j = 2}^{k - 2} q_j \cdot \frac{1}{n - j + 1} + q_{k - 1} \cdot \frac{1}{n - k + 2} \\ &= q_{k - 1} + q_{k - 1} \cdot \frac{1}{n - k + 2} \\ &= q_{k - 1} \cdot \frac{n - k + 3}{n - k + 2} \end{aligned}$$ となる．$q_2 = \frac{1}{n}$ と合わせると

$$q_k = \frac{1}{n - k + 2}$$

と計算できるから，求める確率は $1 - q_k = \frac{n - k + 1}{n - k + 2}$ である．