ひたすら受験問題を解説していくブログ
大阪大学2013年数学第5問
handai_2013_math_5q.png
(1)は簡単ですが、(2)はそれなりに難しいです。それでも本当に頭がいい人は10秒ぐらいで解ける設問であったりもします(直接法参照、もっといいのがあるかもしれませんが)。一応iについての漸化式(求める確率はi=n-1ということです)を立てる方法を2つ、直接法を1つ、(追記として)nについての漸化式を求める方法を1つ提示いたします。一体、阪大さんはどんな解答を最もあり得る解答に想定してたんでしょうか。

解答

解法のポイント
  • とりあえず具体的iな数字で計算してみる
  • 求めたい集合を表すのが難しいなら補集合で考えてみる
  • 似ている要素(形)が出てきたらその理由を考える

(1)
直接で少し面倒だと思ったら、背理法でいけないか考えます。つまりKnがH1にもHnにもはいらない場合を考えて矛盾をつきます。この際にAならばBのAにあたる部分(Bは証明すべきものです)がパッと見みつかりませんが、Aは行なっている操作になります。

KnがH1にもHnにもはいらないのは、H1もHnも埋まっていて、KnがHi(2≦i≦n-1)に入る場合です。ということはKiにおいて、Hiが空にもかかわらずHiに入らないことが必要になります。しかしながら、これは問題文にある玉の入れ方と矛盾します。

というかKiはHk(k=1 or i≦k≦n)に入ることが同様に証明できます。

(2)
題意はつかめても結局何をすればいいのか不明です。nとかiに関するものなので、直接求めるか、漸化式立ててとくか予想して数学的帰納法かといったあたりを模索することになります。

こういう問題では大抵nとかiとかが1,2,3だのの時の値を(1)とかで求めさせることが多いので、ここでもそれにならって求めてみます。i=1,2,3,4(i=1だけは入れ方が違うのでおまけみたいなものです)について求めてみますが、補集合で考えたほうがほんの少しだけわかりやすいので、補集合を求めます(補集合じゃなくても同じ考え方でいけます)。
i=1の場合
H1に入らない確率はn個の箱のうちでH1以外に入る確率なので、(n-1)/nとなります。

i=2の場合
i=2の段階でH2があいていると入るので、あいていないことが条件です。つまりi=1のときに2に入っている必要があります。よって1/nです。

i=3の場合
i=2と同様に考えると、i=2までにH3を埋めてやる必要があります。i=1で埋まる場合と、i=2で埋まる場合を考えます。i=1で埋まるときは均等なので1/nで埋まります。i=2で埋まる場合はi=2のときにH2が埋まっていなければなりません。よって、1/n×1/(n-1)となります。和をとると1/(n-1)になります。

i=4の場合
同様に考えるとi=1で埋まる場合は1/nでi=2で埋まる場合は1/n×1/(n-1)、i=3で埋まる場合は1/(n-1)×1/(n-2)、和をとると1/(n-2)になります。

ここまで来ると規則性が見えてくるのではないでしょうか。つまり、求める確率(補集合でない)をPiとすると、
handai_2013_math_5a-1.png
が成立すると推測できます。i=kまでは、k+1以降の箱は同じように扱われます。つまり、i=kまでのすべてのiにおいて、Hk+1を埋める確率も、Hk+2を埋める確率も同じということです。なので、Hk+1を埋めると見せかけてHk+2を埋めてやればHk+2が埋まる確率を出せることになります。しかしながら、二つの場合には違いがひとつだけあります、Kk+1を入れる操作が余分にあるということです。なのでこれを計算するとKk+1を入れる際にHk+1が埋まっており、かつ、Hk+2にいれるということになるので、上の漸化式になります。
あとは数学的帰納法でいくか漸化式を解くかです。どちらもさほど変わらないので普通に解きます。
handai_2013_math_5a-5.png
尚、漸化式のはじめをi=2と考えているのはi=1のみ入れ方が違って別物だからです。

(2)別解答1


私が最初に解いたときはこんな解答でした編です。試行錯誤をしないため、上より複雑に考えますが、iに関する漸化式を別の考えで導きます。
(1)でi=nのときには1の箱かnの箱にしか入らないとあり、求めるべきn-1の場合はnから近いので、関係式を立てて直接求められないか考えました。しかしながら、1の箱だけ特別であり、それが埋まっている確率がわからないと計算できません。
よって、iを入れるときにH1が空の確率をQiとして連立漸化式を立てることを目指しました(実のところは(1)はnではなく拡張して証明したので、n-1とnからではなくいきなりiとi+1でたてましたが)。
(i)iまでH1が空ではないとき
2からi-1の箱(iまでに必ずうまります)でi-2個、1の箱で1個なので、玉の数と箱の数があうため、1からi-1の箱がすべて埋まり、それ以外が埋まっていない状態です。よってKiは必ずHiに入るので、Pi'=1-Qiで求まります。

(ii)iまでH1が空のとき
i-1までの玉においてこれらは区別されないため、HiからHnが埋まる確率は等確率です。Hiが埋まっていなければよいので、つまりPi''=Qi・(n-i)/(n-i+1)となります。

(i)(ii)より
handai_2013_math_5a-3.png
となります。あとはもう一本式が立てば解けるので、今度はQiを別の考えで表してやることを考えました。
結局のところ連立って感じにはならなかったのですが、i-1を入れるところまでは1の箱もiからnの箱も区別ができません。なので1の箱が空いている確率Qi=Piが成立します(iの箱が空いていれば入るし、開いていなければ入らんので)。
上で求めた関係式と連立させれば、
handai_2013_math_5a-4.png

(2)別解答2


ここまで読んでいただければもうお気づきだと思います。はじめに頭の良いお方は10秒で解けるといったのはこういうことです(残念ながら私は上の方法で解いた後に気づきましたが)。
i-1を入れるところまでは1の箱もiからnの箱も区別ができません。なのでそれらの箱が空いている確率は等しくなっています。つまり、iを入れる段階ではn-i+1個の箱が空いており、1の箱とiからnの箱の数はn-i+2なのでこれらを除した(n-i+1)/(n-i+2)がiの箱が空、つまりiの玉がiの箱に入る確率です、よって2/3。

(2)別解答3


nについて漸化式を立てるものです。自分と同じ番号の箱が埋まっている場合の操作が、1回目の操作と同じこと、ある箱に違う番号の箱が入ったら箱の番号-1までは自分の箱に入れること、を利用して漸化式をたてます。
まず1回目の操作でK1がH1に入れば、他のすべての玉が自分と同じ番号の箱にはいれます。この確率は1/nです。
次に、K1がHnに入る場合も、1とn以外のすべての玉が自分と同じ番号の箱にはいれます。この確率は1/nです。
最後に、上であげた以外の箱Hiに入る場合(確率は1/nです)を考えると、iまでの箱は空いています(箱の個数と入っている玉の数を考えれば証明は容易)。よって、Ki-1までは自分と同じ番号の箱に入るので無視できます。Kiを入れる時はK1を入れる時と同じ操作になるので、求める確率をPnとすれば、Pn-i+1と同じ確率になります。よって、Pn-i+1/nになります。

以上をまとめるとPn=2/n+(Pn-1+Pn-2+・・・・P3)/nとなります。数列の和を含む漸化式なので、数列の和の問題でよくみかけるn+1とnの差を取れるように、両辺にnをかけてからn+1とnで差をとると、(n+1)Pn+1-nPn=Pnとなり、Pn+1=Pn=一定だとわかります。P3を求めると2/3と計算できるので、答えは2/3です。
スポンサーサイト

テーマ:大学受験 - ジャンル:学校・教育

コメント
コメント
コメントの投稿
URL:
本文:
パスワード:
非公開コメント: 管理者にだけ表示を許可する
 
トラックバック
トラックバック URL
http://jukenkaisetsu.blog.fc2.com/tb.php/120-41347129
この記事にトラックバックする(FC2ブログユーザー)
トラックバック