\(n\) を \(3\) 以上の整数とする. \(n\) 個の球 \(K _ 1 , K _ 2 , \cdots , K _ n\) と \(n\) 個の空の箱 \(H _ 1 , H _ 2 , \cdots , H _ n\) がある. 以下のように, \(K _ 1 , K _ 2 , \cdots , K _ n\) の順番に, 球を箱に \(1\) つずつ入れていく. まず, 球 \(K _ 1\) を箱 \(H _ 1 , H _ 2 , \cdots , H _ n\) のどれか \(1\) つに無作為に入れる. 次に球 \(K _ 2\) を, 箱 \(H _ 2\) が空ならば箱 \(H _ 2\) に入れ, 箱 \(H _ 2\) が空でなければ残りの \(n-1\) 個の空の箱のどれか \(1\) つに無作為に入れる. 一般に, \(i = 2, 3, \cdots , n\) について, 球 \(K _ i\) を, 箱 \(H _ i\) が空ならば箱 \(H _ i\) に入れ, 箱 \(H _ i\) が空でなければ残りの \(n-i+1\) 個の空の箱のどれか \(1\) つに無作為に入れる.
(1) \(K _ n\) が入る箱は \(H _ 1\) または \(H _ n\) である. これを証明せよ.
(2) \(K _ {n-1}\) が \(H _ {n-1}\) に入る確率を求めよ.
【 解 答 】
(1)
与えられたルールに従えば, 球 \(K _ {i} \ ( 2 \leqq i \leqq n )\) を箱に入れ終えれば, 箱 \(H _ i\) は空ではなくなる. ただし, 箱 \(H _ 1\) が空であるかは定まっていない.
したがって, 球 \(K _ {n-1}\) を箱に入れ終わったとき, 空である箱は \(H _ 1\) か \(H _ n\) である.
よって, 題意は示された.
(2)
- [P]：「 球 \(K _ {i} \ ( 1 \leqq i \leqq n-1 )\) を箱に入れ終えたとき, \(n-i+1\) 個の箱 \(H _ {1}\) と \(H _ {i+1} , \cdots , H _ {n}\) のうち \(1\) つだけに球が入っている. 各箱が空ではない確率は等しく \(p _ i = \dfrac{1}{n-i+1}\) である. 」
\(1 \leqq i \leqq n-1\) について, [P] が成立することを数学的帰納法を用いて示す.
1* \(i=1\) のとき
\(n\) 個の箱 \(H _ 1 , \cdots , H _ n\) それぞれについて, 球が入っている確率は, \(\dfrac{1}{n}\) であり, [P] が成立する.2* \(i = j \ ( 1 \leqq j \leqq n-2 )\) のとき
[P] が成立すると仮定する. 球 \(K _ {j+1}\) を箱に入れるとき箱 \(H _ {j+1}\) が空であれば, 球 \(K _ {j+1}\) は箱 \(H _ {j+1}\) に入り, 残りの箱の状態は変化しない.
箱 \(H _ {j+1}\) が空でなければ, 残りの空の箱のいずれかに球 \(K _ {j+1}\) が入る.
1* 2*より, \(1 \leqq i \leqq n-1\) について, [P] が成立することが示された.
したがって, \(i = n-2\) のときを考えると
\[
p _ {n-2} = \dfrac{1}{n-(n-2)+1} = \dfrac{1}{3} \ .
\]
つまり, 球 \(K _ {n-1}\) を入れるときに, 箱 \(H _ {n-1}\) が空ではない確率は \(\dfrac{1}{3}\) である.
よって, 求める確率は
\[
1 -\dfrac{1}{3} = \underline{\dfrac{2}{3}} \ .
\]