Evolton

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

nを3以上の整数とする.n個の球K1, K2, ⋯ , Knと
n個の空(から)の箱H1, H2, ⋯ , Hnがある.
以下のように,K1, K2, ⋯ , Knの順番に,球を箱に1つずつ入れていく.

まず,球K1を箱H1, H2, ⋯ , Hnのどれか1つに無作為に入れる.
次に,球K2を,箱H2が空ならば箱H2に入れ,
箱H2が空でなければ残りのn−1個の空の箱のどれか1つに無作為に入れる.

一般に,i=2, 3, ⋯ , nについて,
球Kiを,箱Hiが空ならば箱Hiに入れ,
箱Hiが空でなければ残りのn−i+1個の空の箱のどれか1つに無作為に入れる.

(1) Knが入(はい)る箱はH1またはHnである.これを証明せよ.

(2) Kn−1がHn−1に入る確率を求めよ.

難易度6/ 10計算量4/ 10目安22分

確率、場合の数 状態分類、対称性の利用、条件付き確率

方針

自分の箱が埋まっていた球だけが無作為選択を起こし、その選択先の番号まで連鎖が進むと捉える。(1)は連鎖が H1 または Hn に到達して終わることを示す。(2)は H1,Hn−1,Hn のうち連鎖で最初に選ばれる箱が対称であることを使う。

解答

(1)
K1 が H1 に入れば、以後は各球が自分の箱に入り、Kn は Hn に入る。K1 が Hj (2≦j≦n) に入ると、Kj の番に無作為選択が起こり、選べる空箱はH1,Hj+1,…,Hnである。途中の Hl (j<l<n) を選ぶと、同じ状況が Kl の番に移る。連鎖の番号は必ず大きくなるため、最終的には H1 または Hn が選ばれる。前者なら Kn は Hn、後者なら最後に空いた H1 に入る。したがってKn が入る箱は H1 または Hnである。

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

Kn−1 が自分の箱に入れるかを決めるH1,Hn−1,Hnの3箱に注目する。連鎖で最初に現れる箱は対称で、それぞれ確率 1/3 である。Hn−1 が最初なら失敗し、H1 または Hn が先なら連鎖が終わって Hn−1 は空のまま残る。

よって求める確率は13+13=23である。

別解

解法2(失敗確率の後退帰納)

方針

(1) は「最初の i 箱のうち空箱があるなら、それは H1 だけ」という不変条件で示す。(2)では、Ki の番に Hi が埋まっている状態から Hn−1 を先に埋める確率を qi とおく。後ろから qi=1/3 を示し、最初の K1 の選択へ戻る。

解答

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

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

(2)
まず n≧4 とする。Ki の番に Hi がすでに埋まっているとき、Kn−1 の番より前に Hn−1 が埋まる確率を qi とする。

このとき選べる n−i+1 個の箱はH1,Hi+1,…,Hnである。Hn−1 なら成功、H1,Hn なら失敗、Hj (i<j<n−1) なら確率 qj の状態へ移るからqi=1+∑j=i+1n−2qjn−i+1.i=n−2 では候補が3箱なのでqn−2=13.qi+1,…,qn−2 がすべて 1/3 ならqi=1+(n−i−2)⋅13n−i+1=13.後退帰納法によりqi=13(2≦i≦n−2)である。

K1 が Hn−1 を選ぶと失敗し、Hj (2≦j≦n−2) を選ぶと確率 qj で失敗する。よって失敗確率は1n(1+∑j=2n−2qj)=1n(1+(n−3)13)=13.よって、自分の箱に入る確率は1−13=23.n=3 のときも、K1 が H2 を選ぶ場合だけ K2 が自分の箱に入らないので、求める確率は 2/3 である。

総評

難度6、目安時間22分。乱択が起こるのは、自分の箱を先取りされた球だけであり、連鎖の番号は必ず大きくなる。解法1は3箱の相対順序の対称性を使う短い解法、解法2は失敗確率を後退帰納で 1/3 と示す計算的な解法である。「対称だから」とだけ書かず、どの3箱の何が同確率なのかを明示することが重要である。

Evolton Pro

月額
2,480円(税込)
保存・印刷
公開過去問PDF・オーダーメイド問題集PDF
プランを確認・登録

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

出典: 大阪大学 2013年度 前期日程 数学(大学公式の問題PDF)。問題文はHTML表示のために再入力・数式組版しています。