トップ› 大阪大学› 2013年› 理系第5問

大阪大学 2013年理系第5問解説

方針・初手

各ステップにおいて「どの箱に球が入っているか（どの箱が空いているか）」の状態に着目する。 (1) では、各球を入れ終わった直後の空き箱の状況に規則性があることを見抜き、それを数学的帰納法で証明する。 (2) では、(1) で整理した状態の推移に基づき、特定の箱に球が入っている確率に関する漸化式を立てて求める。

解法1

(1)

$i = 2, 3, \cdots, n$ について、球 $K_{i-1}$ を入れ終わった直後の箱の状態に関する次の命題 $P(i)$ を数学的帰納法で示す。

$P(i)$：「全体の空き箱は $n-i+1$ 個であり、それは箱 $H_1, H_i, H_{i+1}, \cdots, H_n$ のうちの $n-i+1$ 個である。言い換えると、これら $n-i+2$ 個の箱のうちちょうど1つに球が入っており、他の箱はすべて空いている」

(I)

$i=2$ のとき球 $K_1$ は $H_1, H_2, \cdots, H_n$ のいずれか1つに入れられる。したがって、全体の空き箱は $n-1$ 個であり、それらは $H_1, H_2, \cdots, H_n$ のうちの $n-1$ 個である。よって、$P(2)$ は成り立つ。

(II)

$i=k$ （$2 \le k \le n-1$）のとき、$P(k)$ が成り立つと仮定する。球 $K_{k-1}$ を入れ終わった直後、箱 $H_1, H_k, H_{k+1}, \cdots, H_n$ のうち、ある1つの箱 $H_m$ （$m \in \{1, k, k+1, \cdots, n\}$）にのみ球が入っており、これらの中の他の箱はすべて空いている。次に、球 $K_k$ を入れる操作を考える。

(i)

$H_m \neq H_k$ のとき箱 $H_k$ は空いているので、規則により $K_k$ は $H_k$ に入れられる。この結果、新たに $H_k$ に球が入る。もともと球が入っていたのは $H_m$ であり、$H_k \neq H_m$ であるから、球が入っている箱は $H_m$ と $H_k$ になる。これより後の空き箱は、もとの空き箱から $H_k$ を除いたものである。対象の箱を $H_1, H_{k+1}, \cdots, H_n$ に絞ると、この中で球が入っているのは $H_m$ のみとなる。よって、$P(k+1)$ は成り立つ。

(ii)

$H_m = H_k$ のとき箱 $H_k$ にはすでに球が入っている。規則により、$K_k$ は残りの空き箱のいずれかに無作為に入れられる。残りの空き箱とは、箱 $H_1, H_{k+1}, \cdots, H_n$ の $n-k+1$ 個すべてである。 $K_k$ がこれらのうちの1つ（これを $H_l$ とする）に入れられると、新たに $H_l$ に球が入る。対象の箱 $H_1, H_{k+1}, \cdots, H_n$ の中で球が入っているのは $H_l$ のみとなり、他は空いている。よって、$P(k+1)$ は成り立つ。

（I）, （II）より、すべての $i=2, 3, \cdots, n$ について $P(i)$ は成り立つ。特に $i=n$ のとき、$P(n)$ より全体の空き箱は $n-n+1 = 1$ 個であり、それは $H_1$ と $H_n$ のいずれかである。最後に球 $K_n$ はこの唯一の空き箱に入れられるため、$K_n$ が入る箱は $H_1$ または $H_n$ である。（証明終）

(2)

球 $K_{n-1}$ を入れる規則について考える。 $K_{n-2}$ を入れ終わった直後に箱 $H_{n-1}$ が空いている場合、$K_{n-1}$ は必ず $H_{n-1}$ に入れられる。逆に、$H_{n-1}$ にすでに球が入っている場合、$K_{n-1}$ は他の空き箱に入れられるため、$H_{n-1}$ には入らない。したがって、求める確率は「$K_{n-2}$ を入れ終わった直後に $H_{n-1}$ が空いている確率」である。

(1) の証明より、$i=2, 3, \cdots, n$ に対して、球 $K_{i-1}$ を入れ終わった直後に、箱 $H_1, H_i, H_{i+1}, \cdots, H_n$ のうちちょうど1つの箱に球が入っている。この「球が入っている1つの箱」が $H_m$ （$m \in \{1, i, i+1, \cdots, n\}$）である確率を $p_{i, m}$ とおく。

$i=2$ のとき、球 $K_1$ は $H_1, \cdots, H_n$ に無作為に入れられるため、各 $m \in \{1, 2, \cdots, n\}$ について

$$ p_{2, m} = \frac{1}{n} $$

である。次に、$i=k$ から $i=k+1$ への推移を考える（$2 \le k \le n-1$）。 $K_k$ を入れ終わった直後に箱 $H_m$ （$m \in \{1, k+1, \cdots, n\}$）に球が入っている事象は、次の2つの排反な事象の和事象である。

(ア)

$K_{k-1}$ を入れ終わった直後に $H_m$ に球が入っており、$K_k$ が $H_k$ に入る場合。この事象が起こる確率は $p_{k, m} \times 1 = p_{k, m}$ である。

(イ)

$K_{k-1}$ を入れ終わった直後に $H_k$ に球が入っており、$K_k$ が $n-k+1$ 個の空き箱の中から $H_m$ に入る場合。この事象が起こる確率は $p_{k, k} \times \frac{1}{n-k+1}$ である。

これらより、次の漸化式が成り立つ。

$$ p_{k+1, m} = p_{k, m} + p_{k, k} \times \frac{1}{n-k+1} $$

ここで、任意の $i=2, 3, \cdots, n$ について、確率分布が一様であり

$$ p_{i, m} = \frac{1}{n-i+2} \quad (m \in \{1, i, i+1, \cdots, n\}) $$

であることを数学的帰納法で示す。

(I)

$i=2$ のときは $p_{2, m} = \frac{1}{n}$ であり成り立つ。 (II)

$i=k$ で成り立つと仮定すると、$p_{k, m} = p_{k, k} = \frac{1}{n-k+2}$ であるから、

$$ \begin{aligned} p_{k+1, m} &= \frac{1}{n-k+2} + \frac{1}{n-k+2} \times \frac{1}{n-k+1} \\ &= \frac{1}{n-k+2} \left( 1 + \frac{1}{n-k+1} \right) \\ &= \frac{1}{n-k+2} \times \frac{n-k+2}{n-k+1} \\ &= \frac{1}{n-k+1} \end{aligned} $$

となり、$i=k+1$ のときも成り立つ。したがって、すべての $i$ について上の式が成り立つ。

求める確率は、$K_{n-2}$ を入れ終わった直後に $H_{n-1}$ が空いている確率である。これは $i=n-1$ の状況に該当するため、

$$ \begin{aligned} 1 - p_{n-1, n-1} &= 1 - \frac{1}{n-(n-1)+2} \\ &= 1 - \frac{1}{3} \\ &= \frac{2}{3} \end{aligned} $$

となる。

解説

複雑に見える操作だが、「その時点でどの箱が埋まっているか（空いているか）」という状態の集合を正しく捉えることで、見通しよく解くことができる。 (2) で示したように、対象となる箱に対して常に一様分布が保たれる（どの箱も等確率で球が入っている）という美しい構造を持った問題である。抽象的な $n$ のままでは分かりにくい場合、$n=3, 4$ などの小さい値で実験をして規則性を予想することが非常に有効なアプローチとなる。