京都大学 2009年度理系乙数学理系乙第3問解答・解説

問題

$n$ 枚のカードを積んだ山があり、各カードには上から順番に1から $n$ まで番号がつけられている。ただし $n ≧ 2$ とする。このカードの山に対して次の試行を繰り返す。1回の試行では、一番上のカードを取り、山の一番上に戻すか、あるいはいずれかのカードの下に入れるという操作を行う。これら $n$ 通りの操作は全て同じ確率であるとする。 $n$ 回の試行を終えたとき、最初一番下にあったカード（番号 $n$ ）が山の一番上にきている確率を求めよ。

出典：京都大学 2009年度前期日程第2次学力試験（理系乙）理系乙理系乙第3問

方針

番号 $n$ のカードより上にあるカードの枚数を状態 $k$ とする。 $k > 0$ のとき、1回の操作で $k$ はそのままか1だけ減り、減る確率は $(n - k) / n$ 、そのままの確率は $k / n$ である。初期値 $n - 1$ から $n$ 回後に0となるには、最初の $n - 1$ 回で全て減って最後に番号 $n$ を一番上へ戻す場合と、正の状態のどこかで1回だけ停滞する場合の2種類しかない。

解答

番号 $n$ のカードより上にあるカードの枚数を $k$ とする。 $k > 0$ のとき、一番上のカードを取り除いた直後は上のカードが $k - 1$ 枚になる。取り出したカードを番号 $n$ のカードより上へ戻す方法は $k$ 通り、下へ入れる方法は $n - k$ 通りである。したがって

P (k \to k) = \frac{k}{n}, P (k \to k - 1) = \frac{n - k}{n} .

初めは $k = n - 1$ であり、1回の試行で $k$ は高々1しか減らない。

まず、最初の $n - 1$ 回で毎回 $k$ が1ずつ減る確率を $p$ とすると

p = \frac{1}{n} \cdot \frac{2}{n} \dots \frac{n - 1}{n} = \frac{( n - 1 )!}{n ^{n - 1}} .

この後は番号 $n$ のカード自身が一番上にある。第 $n$ 回でこのカードを再び一番上へ戻す確率は $1/ n$ だから、この場合の確率は $p / n$ である。

次に、第 $n$ 回で初めて $k = 0$ となる場合を考える。この場合、 $n$ 回のうち $n - 1$ 回は $k$ が1減り、残る1回だけ正の状態 $k$ にとどまる。この停滞が状態 $k$ で起こる確率は、全て減る経路の確率 $p$ に $k / n$ を掛けたものである。 $k = 1, 2, \dots, n - 1$ を合計すると

p k = 1 \sum n - 1 \frac{k}{n} = p \frac{n - 1}{2} .

以上の2つの場合は互いに排反であり、これら以外には $n$ 回で $k = 0$ になれない。したがって求める確率は

\frac{( n - 1 )!}{n ^{n - 1}} (\frac{1}{n} + \frac{n - 1}{2}) = \frac{( n - 1 )! { n ( n - 1 ) + 2 }}{2 n ^{n}} .

京都大学 2009年度理系乙数学 理系乙 第3問

問題

方針

解答

京都大学 2009年度
理系乙数学理系乙第3問