京都大学 2018年 文系 第5問 解説

方針・初手

$m$ 回目の操作を行う直前、袋の中には $m$ 個の球が入っており、そのうち「$0$」が書かれた球は常に1個だけであることを把握します。

また、操作(ii), (iii) のルールから、「$0$」を取り出すたびに袋の中の数の最大値が1ずつ増え、「$0$ 以外」を取り出したときはその時点ですでに存在する数と同じ数が追加されることに着目します。

この性質から、袋の中の数の合計 $X_n$ のとり得る最大値と最小値を評価し、条件を満たす事象を特定します。

解法1

(1)

$m$ 回目の操作直前、袋の中の球は $m$ 個であり、そのうち「$0$」は1個のみである。

与えられた不等式の右辺を変形すると、

$$ \frac{(n+2)(n-1)}{2} = \frac{n(n+1)}{2} - 1 $$

となる。

$n$ 回の操作で「$0$」を引く回数を $r$ とし、残りの $n-r$ 回は「$0$ 以外」を引くとする。

「$0$」を $r$ 回引くことで、袋には新しく $1, 2, \ldots, r$ の数が1つずつ追加される。「$0$ 以外」を引いたときは既存の数が複製されるが、引ける数の最大値は引く直前の袋の最大値であるため、$r$ 以下である。

したがって、$n$ 回の操作後に追加された数の合計 $X_n$ は、

$$ X_n \leq \frac{r(r+1)}{2} + r(n-r) = \frac{r(2n-r+1)}{2} $$

これを $f(r)$ とおく。$f(r)$ は上に凸の2次関数であり、$1 \leq r \leq n$ の範囲で単調増加する。

• $r = n$ のとき、$f(n) = \dfrac{n(n+1)}{2}$
• $r = n-1$ のとき、$f(n-1) = \dfrac{(n-1)(n+2)}{2} = \dfrac{n(n+1)}{2} - 1$
• $r \leq n-2$ のとき、$f(r) \leq f(n-2) = \dfrac{(n-2)(n+3)}{2} = \dfrac{n(n+1)}{2} - 3 < \dfrac{n(n+1)}{2} - 1$

よって、$X_n \geq \dfrac{n(n+1)}{2} - 1$ となるのは、以下の2つの事象のいずれかである。

[A] $n$ 回すべて「$0$」を引く場合 $\left(X_n = \dfrac{n(n+1)}{2}\right)$

$j$ 回目の操作直前の袋に「$0$」は1個しかないため、「$0$」を引く確率は $\dfrac{1}{j}$ である。よって、

$$ P(A) = 1 \cdot \frac{1}{2} \cdot \frac{1}{3} \cdots \frac{1}{n} = \frac{1}{n!} $$

[B] 「$0$」を $n-1$ 回、「$0$ 以外」を1回引き、$X_n = \dfrac{n(n+1)}{2} - 1$ となる場合

「$0$ 以外」を引くのが $k$ 回目 ($2 \leq k \leq n$) だとする。そのとき袋の最大値は $k-1$ であるため、追加される数 $x$ は $x \leq k-1$ である。最終的な合計は

$$ X_n = \frac{(n-1)n}{2} + x $$

となるため、これが $\dfrac{n(n+1)}{2} - 1$ と等しくなるには $x = n-1$ が必要である。$x \leq k-1 \leq n-1$ より、これを満たすのは $k = n$ かつ $x = n-1$ のときのみである。

すなわち、$n-1$ 回目まで連続して「$0$」を引き、袋の中が $\{0, 1, 2, \ldots, n-1\}$ となっている状態から、$n$ 回目に「$n-1$」を引く事象に限られる。

$$ P(B) = \frac{1}{(n-1)!} \cdot \frac{1}{n} = \frac{1}{n!} $$

[A] と [B] は排反であるため、求める確率は

$$ P(A) + P(B) = \frac{1}{n!} + \frac{1}{n!} = \frac{2}{n!} $$

(2)

$n$ 回の操作終了後、袋の中には「$0$」が1個と、1以上の整数が $n$ 個入っている。したがって、それらの合計 $X_n$ は必ず $X_n \geq n$ となる。条件 $X_n \leq n+1$ を満たすのは、$X_n = n$ または $X_n = n+1$ のときである。

[C] $X_n = n$ となる場合

追加される $n$ 個の数がすべて「$1$」である場合である。1回目は必ず「$0$」を引き「$1$」が追加される。2回目以降はずっと「$1$」を引き続ける必要がある。$j$ 回目の操作直前、袋の中は「$0$」が1個、「$1$」が $j-1$ 個であるため、「$1$」を引く確率は $\dfrac{j-1}{j}$ である。

$$ P(C) = 1 \cdot \frac{1}{2} \cdot \frac{2}{3} \cdots \frac{n-1}{n} = \frac{1}{n} $$

[D] $X_n = n+1$ となる場合

追加される $n$ 個の数が「$2$」が1個、「$1$」が $n-1$ 個である場合である。「$2$」が追加されるのは、袋の最大値が1のときに「$0$」を引いたときのみである。袋の最大値が1になるのは1回目の操作後であるから、2回目以降の $n-1$ 回の操作のうち、ある $k$ 回目 ($2 \leq k \leq n$) にちょうど1回だけ「$0$」を引き、他はすべて「$1$」を引く事象である。

この事象の確率は $k$ の値によらず一定となる。各段階の確率を計算すると、

• 1回目：「$0$」を引く（確率 $1$）
• $2 \sim k-1$ 回目：「$1$」を引く（確率の積 $\dfrac{1}{2} \cdot \dfrac{2}{3} \cdots \dfrac{k-2}{k-1} = \dfrac{1}{k-1}$）
• $k$ 回目：「$0$」を引く（確率 $\dfrac{1}{k}$）
• $k+1 \sim n$ 回目：「$1$」を引く（直前の袋には「$0$」が1個、「$2$」が1個、「$1$」が $j-2$ 個あるため、確率は $\dfrac{j-2}{j}$）

$k+1$ から $n$ 回目までの確率の積は、

$$ \prod_{j=k+1}^{n} \frac{j-2}{j} = \frac{(k-1) \cdot k}{n(n-1)} $$

したがって、

$$ P(D_k) = 1 \cdot \frac{1}{k-1} \cdot \frac{1}{k} \cdot \frac{(k-1)k}{n(n-1)} = \frac{1}{n(n-1)} $$

$k$ は $2, 3, \ldots, n$ の $n-1$ 通りあるので、

$$ P(D) = (n-1) \cdot \frac{1}{n(n-1)} = \frac{1}{n} $$

[C] と [D] は排反であるため、求める確率は

$$ P(C) + P(D) = \frac{1}{n} + \frac{1}{n} = \frac{2}{n} $$

解説

操作ごとの確率の推移を追いかけるだけでなく、$X_n$ が取り得る値の「最大値・最小値」からの絞り込みが要求される問題です。

各操作において「$0$」は袋に1つしか存在しないため、球の総数が $m$ 個のとき「$0$ 以外」を引く確率は常に $\dfrac{m-1}{m}$ となります。

(1) では、与えられた不等式が「最大値」と「最大値 $-1$」の2パターンしかないことを見抜けるかが鍵です。$f(r) = \dfrac{r(2n-r+1)}{2}$ の最大値評価により、$r \leq n-2$ の場合は条件を満たせないことを示します。

(2) においても同様に、$X_n \geq n$ であることから「最小値」と「最小値 $+1$」の2パターンに絞られます。(2) の確率計算で現れる積の計算は、分子と分母が連鎖的に相殺される形になり、最終的に $k$ に依存しない結果 $\dfrac{1}{n(n-1)}$ が得られます。

答え

(1)

$$ \frac{2}{n!} $$

(2)

$$ \frac{2}{n} $$