京都大学 2018年度文系数学第5問解答・解説

問題

整数が書かれている球がいくつか入っている袋に対し，次の一連の操作を考える。ただし，各球に書かれている整数は1つだけとする。

(i)袋から無作為に球を1個取り出し，その球に書かれている整数を $k$ とする。

(ii) $k \neq = 0$ の場合，整数 $k$ が書かれた球を1個新たに用意し，取り出した球とともに袋に戻す。

(iii) $k = 0$ の場合，袋の中にあった球に書かれていた数の最大値より1大きい整数が書かれた球を1個新たに用意し，取り出した球とともに袋に戻す。

整数0が書かれている球が1個だけ入った袋から始める。この袋に上の操作を $n$ 回繰り返した後，袋の中にある $n + 1$ 個の球に書かれた数の合計を $X_{n}$ とする。例えば $X_{1}$ は常に1である。以下， $n ≧ 2$ とする。

(1)

X_{n} ≧ \frac{( n + 2 ) ( n - 1 )}{2}

である確率を求めよ。

(2) $X_{n} ≦ n + 1$ である確率を求めよ。

出典：京都大学 2018年度前期日程第2次学力試験文系第5問

方針

解法1

操作後の和は，0を取り出すと新しい最大値が1つ増え，正の数を取り出すとその数がもう1つ増えると考える。(1)のしきい値は最大和 $1 + 2 + \dots + n$ より1だけ小さいので，最大または最大より1小さい操作列だけを数えればよい。(2)では各回で少なくとも1ずつ和が増えるため $X_{n} ≧ n$ であり， $X_{n} = n$ と $X_{n} = n + 1$ になる極端な列を直接数える。確率は，各時刻の袋の中の球数と，該当する数が書かれた球の個数を追って掛け合わせる。

解法2

各回に新しく加わる数を，最大列 $1, 2, \dots, n$ からの「不足」と，最小列 $1, 1, \dots, 1$ からの「超過」で評価する。(1)では不足が高々1，(2)では超過が高々1となる操作列を分類する。分類後の確率は，その時点の球総数と1が書かれた球の個数から積を作り，望ましい形に約分する。

解答

解法1

(1)

和を最大にするには，毎回0が書かれた球を取り出せばよい。このとき1回ごとに新しい数が作られ， $n$ 回後の正の数は $1, 2, \dots, n$ である。したがって最大値は $1 + 2 + \dots + n = \frac{n ( n + 1 )}{2}$ である。問題の条件は $X_{n} ≧ \frac{( n + 2 ) ( n - 1 )}{2} = \frac{n ( n + 1 )}{2} - 1$ であり，最大値より1小さい値以上を求めている。

最大値になるのは， $n$ 回すべてで0を取り出す場合だけである。この確率は， $j$ 回目の操作直前に袋の中の球が $j$ 個あることから $1 \cdot \frac{1}{2} \cdot \frac{1}{3} \dots \frac{1}{n} = \frac{1}{n !}$ である。

次に最大値より1小さい値になる場合を考える。最初の $n - 1$ 回で0を取り出すと，袋には0と $1, 2, \dots, n - 1$ が1個ずつ入っている。最後に0ではなく $n - 1$ と書かれた球を取り出せば，増える値が $n$ ではなく $n - 1$ になるので，和は最大値より1だけ小さくなる。これ以外で0を取り出さない回がもっと早いと，失う値は2以上になるため条件を満たさない。

この場合の確率は $1 \cdot \frac{1}{2} \dots \frac{1}{n - 1} \cdot \frac{1}{n} = \frac{1}{n !}$ である。よって求める確率は $\frac{1}{n !} + \frac{1}{n !} = \frac{2}{n !}$ である。

(2)

各操作では新たに入る球の数は少なくとも1であるから，常に $X_{n} ≧ n$ である。したがって $X_{n} ≦ n + 1$ となるのは， $X_{n} = n$ または $X_{n} = n + 1$ の場合に限られる。

まず $X_{n} = n$ となるには，1回目に0を取り出して1を作り，その後は毎回1と書かれた球を取り出すしかない。2回目以降， $j$ 回目の操作直前には袋の中の球が $j$ 個あり，そのうち1と書かれた球が $j - 1$ 個ある。よって確率は $\frac{1}{2} \cdot \frac{2}{3} \dots \frac{n - 1}{n} = \frac{1}{n}$ である。

次に $X_{n} = n + 1$ となる場合を数える。これは，2回目から $n$ 回目までのどこか1回だけ0を取り出して2を作り，それ以外の回では1を取り出す場合に限られる。0を取り出すのが $m$ 回目 $(2 ≦ m ≦ n)$ であるとする。その前までは1を取り出し， $m$ 回目に0を取り出し，その後は再び1を取り出すので，その確率は

(\frac{1}{2} \cdot \frac{2}{3} \dots \frac{m - 2}{m - 1}) \cdot \frac{1}{m} \cdot (\frac{m - 1}{m + 1} \cdot \frac{m}{m + 2} \dots \frac{n - 2}{n}) = \frac{1}{n ( n - 1 )}

である。この値は $m$ によらない。 $m$ は $n - 1$ 通りあるから $P (X_{n} = n + 1) = \frac{n - 1}{n ( n - 1 )} = \frac{1}{n}$ である。

以上より $P (X_{n} ≦ n + 1) = P (X_{n} = n) + P (X_{n} = n + 1) = \frac{1}{n} + \frac{1}{n} = \frac{2}{n}$ である。

解法2

(1)

毎回0を取り出すと，新しく加わる数は順に

1, 2, \dots, n

となる。したがって

X_{n} ≦ 1 + 2 + \dots + n = \frac{n ( n + 1 )}{2} .

問題のしきい値はこの最大値より1だけ小さい。

最初に0以外を取り出すのが第 $m$ 回だとする。それ以前は0を取り出しているので，第 $m$ 回直前の正の数は $1, 2, \dots, m - 1$ である。ここで $k ≦ m - 1$ を取り出すと，本来加わる $m$ の代わりに $k$ が加わり，少なくとも1不足する。

もし $m < n$ なら，次回以降も最大値の生成が1段遅れるため，最終的な不足は少なくとも2になる。よって不足が高々1となるのは，次の2場合だけである。

場合 最大 最大より 1 小さい 操作列 0 を n 回連続で取り出す 0 を n - 1 回取り出し，最後に n - 1 を取り出す X_{n} \frac{n ( n + 1 )}{2} \frac{n ( n + 1 )}{2} - 1

どちらの確率も

1 \cdot \frac{1}{2} \cdot \frac{1}{3} \dots \frac{1}{n} = \frac{1}{n !}

である。したがって求める確率は

\frac{2}{n !} .

(2)

最小の増分は毎回1なので $X_{n} ≧ n$ である。 $X_{n} = n$ となるには，最初に0を取り出して1を作り，以後は1だけを取り出せばよい。その確率は

\frac{1}{2} \cdot \frac{2}{3} \dots \frac{n - 1}{n} = \frac{1}{n} .

$X_{n} = n + 1$ となるには，基準の増分1を超える操作がちょうど1回だけ必要である。それは第 $m$ 回 $(2 ≦ m ≦ n)$ に0を取り出して2を作り，他の回では1を取り出す場合に限られる。

第 $m$ 回より前，第 $m$ 回，第 $m$ 回より後の確率を分けると

(\frac{1}{2} \cdot \frac{2}{3} \dots \frac{m - 2}{m - 1}) \frac{1}{m} (\frac{m - 1}{m + 1} \cdot \frac{m}{m + 2} \dots \frac{n - 2}{n}) = \frac{1}{m - 1} \cdot \frac{1}{m} \cdot \frac{m ( m - 1 )}{n ( n - 1 )} = \frac{1}{n ( n - 1 )} .

これは $m$ によらず， $m$ は $n - 1$ 通りあるから

P (X_{n} = n + 1) = \frac{1}{n} .

ゆえに

P (X_{n} ≦ n + 1) = P (X_{n} = n) + P (X_{n} = n + 1) = \frac{2}{n} .

京都大学 2018年度文系数学 第5問

問題

方針

解法1

解法2

解答

解法1

(1)

(2)

解法2

(1)

(2)

京都大学 2018年度
文系数学第5問