Evolton

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

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

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

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

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

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

(1) Xn≧(n+2)(n−1)2である確率を求めよ。

(2)
Xn≦n+1 である確率を求めよ。

難易度7/ 10計算量5/ 10目安30分

確率　数え上げ、場合分け、状態分類

方針

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

解答

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

最大値になるのは，n 回すべてで0を取り出す場合だけである。この確率は，j 回目の操作直前に袋の中の球が j 個あることから 1⋅12⋅13⋯1n=1n! である。

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

この場合の確率は 1⋅12⋯1n−1⋅1n=1n! である。よって求める確率は 1n!+1n!=2n! である。

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

まず Xn=n となるには，1回目に0を取り出して1を作り，その後は毎回1と書かれた球を取り出すしかない。2回目以降，j 回目の操作直前には袋の中の球が j 個あり，そのうち1と書かれた球が j−1 個ある。よって確率は 12⋅23⋯n−1n=1n である。

次に Xn=n+1 となる場合を数える。これは，2回目から n 回目までのどこか1回だけ0を取り出して2を作り，それ以外の回では1を取り出す場合に限られる。0を取り出すのが m 回目 (2≦m≦n) であるとする。その前までは1を取り出し，m 回目に0を取り出し，その後は再び1を取り出すので，その確率は(12⋅23⋯m−2m−1)⋅1m⋅(m−1m+1⋅mm+2⋯n−2n)=1n(n−1)である。この値は m によらない。m は n−1 通りあるから P(Xn=n+1)=n−1n(n−1)=1n である。

以上より P(Xn≦n+1)=P(Xn=n)+P(Xn=n+1)=1n+1n=2n である。

別解

解法2

方針

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

解答

(1)

毎回0を取り出すと，新しく加わる数は順に1,2,…,nとなる。したがってXn≦1+2+⋯+n=n(n+1)2.問題のしきい値はこの最大値より1だけ小さい。

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

もし m<n なら，次回以降も最大値の生成が1段遅れるため，最終的な不足は少なくとも2になる。よって不足が高々1となるのは，次の2場合だけである。場合操作列Xn最大0をn回連続で取り出すn(n+1)2最大より1小さい0をn−1回取り出し，最後にn−1を取り出すn(n+1)2−1どちらの確率も1⋅12⋅13⋯1n=1n!である。したがって求める確率は2n!.(2)

最小の増分は毎回1なので Xn≧n である。Xn=n となるには，最初に0を取り出して1を作り，以後は1だけを取り出せばよい。その確率は12⋅23⋯n−1n=1n.Xn=n+1 となるには，基準の増分1を超える操作がちょうど1回だけ必要である。それは第 m 回 (2≦m≦n) に0を取り出して2を作り，他の回では1を取り出す場合に限られる。

第 m 回より前，第 m 回，第 m 回より後の確率を分けると(12⋅23⋯m−2m−1)1m(m−1m+1⋅mm+2⋯n−2n)=1m−1⋅1m⋅m(m−1)n(n−1)=1n(n−1).これは m によらず，m は n−1 通りあるからP(Xn=n+1)=1n.ゆえにP(Xn≦n+1)=P(Xn=n)+P(Xn=n+1)=2n.

総評

難度7、目安時間30分。分布全体を求めず，最大値からの不足と最小値からの超過だけを分類するのが核心である。(1)のしきい値は最大値 n(n+1)/2 より1小さいため，許されるのは全回0，または最後だけ n−1 の2列。(2)は Xn≧n から n,n+1 の場合だけを数える。0を取り出す時刻 m を固定した後半では，1の球の個数が球総数より2少ないことに注意して積を作る。2解法で確率 2/n! と 2/n を相互検算した。

冊子PDFで見る京大の確率の問題で問題集を作る

出典: 京都大学 2018年度 前期日程 第2次学力試験 数学（文系）（大学公式の問題PDF）。問題文はHTML表示のために再入力・数式組版しています。