大阪大学 2013年度 前期日程 第2次学力試験理系数学 第5問

(1)
$K_1$ が $H_1$ に入れば、以後は各球が自分の箱に入り、$K_n$ は $H_n$ に入る。$K_1$ が $H_j$ $(2\leqq j\leqq n)$ に入ると、$K_j$ の番に無作為選択が起こり、選べる空箱は$$H_1,H_{j+1},\dots ,H_n$$である。途中の $H_l$ $(j<l<n)$ を選ぶと、同じ状況が $K_l$ の番に移る。連鎖の番号は必ず大きくなるため、最終的には $H_1$ または $H_n$ が選ばれる。前者なら $K_n$ は $H_n$、後者なら最後に空いた $H_1$ に入る。したがって$$K_n\text{ が入る箱は }{H}_1\text{ または }{H}_n$$である。

(2)
無作為選択が起こるたび、まだ空いている候補箱から1箱を等確率で選ぶ。これは、候補箱を無作為な順序に並べ、必要になるたびに次の有効な箱を読むことと同じである。

$K_{n-1}$ が自分の箱に入れるかを決める$$H_1,H_{n-1},H_n$$の3箱に注目する。連鎖で最初に現れる箱は対称で、それぞれ確率 $1\mathrm{/}3$ である。$H_{n-1}$ が最初なら失敗し、$H_1$ または $H_n$ が先なら連鎖が終わって $H_{n-1}$ は空のまま残る。

よって求める確率は$$\frac{1}{3}+\frac{1}{3}=\frac{2}{3}$$である。

(1) は「最初の $i$ 箱のうち空箱があるなら、それは $H_1$ だけ」という不変条件で示す。(2)では、$K_i$ の番に $H_i$ が埋まっている状態から $H_{n-1}$ を先に埋める確率を $q_i$ とおく。後ろから $q_i=1\mathrm{/}3$ を示し、最初の $K_1$ の選択へ戻る。

(1)
$K_1$ を入れた後、各 $i$ で「$H_1,\dots ,H_i$ はすべて埋まり、未来の箱は未使用」または「この $i$ 箱では $H_1$ だけが空で、未来の箱が1個だけ先取り済み」のどちらかが成り立つ。

前者では次の球が自分の箱に入る。後者では、先取りされた箱の番号に達した球が $H_1$ を選べば前者へ移り、さらに先の箱を選べば後者が続く。よって帰納的に不変である。$i=n-1$ では、前者なら $K_n$ は $H_n$、後者なら $K_n$ は $H_1$ に入る。

(2)
まず $n\geqq 4$ とする。$K_i$ の番に $H_i$ がすでに埋まっているとき、$K_{n-1}$ の番より前に $H_{n-1}$ が埋まる確率を $q_i$ とする。

このとき選べる $n-i+1$ 個の箱は$$H_1,H_{i+1},\dots ,H_n$$である。$H_{n-1}$ なら成功、$H_1,H_n$ なら失敗、$H_j$ $(i<j<n-1)$ なら確率 $q_j$ の状態へ移るから$$q_i=\frac{1+{\displaystyle \sum _{j=i+1}^{n-2}{q}_j}}{n-i+1}\mathrm{.}$$$i=n-2$ では候補が3箱なので$$q_{n-2}=\frac{1}{3}\mathrm{.}$$$q_{i+1},\dots ,q_{n-2}$ がすべて $1\mathrm{/}3$ なら$$\begin{array}{rl}{\displaystyle q_i}& {\displaystyle =\frac{1+(n-i-2)\cdot \frac{1}{3}}{n-i+1}}\\ {\displaystyle }& {\displaystyle =\frac{1}{3}\mathrm{.}}\end{array}$$後退帰納法により$$q_i=\frac{1}{3}(2\leqq i\leqq n-2)$$である。

$K_1$ が $H_{n-1}$ を選ぶと失敗し、$H_j$ $(2\leqq j\leqq n-2)$ を選ぶと確率 $q_j$ で失敗する。よって失敗確率は$$\begin{array}{rl}{\displaystyle \frac{1}{n}(1+\sum _{j=2}^{n-2}{q}_j)}& {\displaystyle =\frac{1}{n}(1+(n-3)\frac{1}{3})}\\ {\displaystyle }& {\displaystyle =\frac{1}{3}\mathrm{.}}\end{array}$$よって、自分の箱に入る確率は$$1-\frac{1}{3}=\frac{2}{3}\mathrm{.}$$$n=3$ のときも、$K_1$ が $H_2$ を選ぶ場合だけ $K_2$ が自分の箱に入らないので、求める確率は $2\mathrm{/}3$ である。