問題15239・・・出会いの泉より http://6626.teacup.com/shochandas/bbs?page=4& GAI様提示問 Orz〜
何枚かのコインがすべて表向きに横一列で並んでいる。 次の条件を満たす表向きのコインを無作為に一枚選んで裏返す。 (表向きコインは何枚も存在するも、選ぶ行為はランダムとする。条件を満たせば裏返せる。)
条件:そのコインより右に裏向きコインが一枚もないか そのコインより左に裏向きコインが一枚もない。 (両端のコインは隣が裏向きでも選ばれればひっくり返し可能)
条件を満たす表向きのコインが無くなるまでこの操作を続ける。
さて操作が終了したとき、裏向きになったコインが10枚以上を期待するためには 最初のコインは何枚以上を並べて置くことが必要になるでしょうか?
解答
・GAI様のもの Orz〜
一般にn個のコインが並んでいるものとし、これにランダムに1からnまでの番号を割り振る。 そして番号の若い順にコインをチェックしていくものとする。 条件を満たすコインは裏返していくものとする。 今左端からk番目のコインが裏返しができるためには、これより左にあるコインには裏向きのコインが無いことで これはk番目に付けられた番号が、それより左に付けられたコインの番号のどれよりも小さい数字であることに対応する。 従ってそのコインが裏返される確率はk種類の数字の中の唯一つの最小の数であることから1/kのものに対応する。(事象A) これは同じように右端から(n+1-k)番目のコインでもあり、これが裏返し可能なものになる確率は同じく1/(n+1-k)が対応。(事象B) 裏返し可能の条件はA∪Bで ここにA∩Bに対する確率は、正にそのk番目のコインに数字1が割り振られていることに対応しているからその確率は1/n 即ちk番目のコインが裏返される確率は1/k+1/(n+1-k)-1/n 従って、裏向きにできるコインの枚数の期待値E(n)は E(n)=Σ[k=1,n](1/k+1/(n+1-k)-1/n)=2*(1+1/2+1/3+・・・+1/n)-1 E(n)>10 を満たす最小のnを調べることでn=137を得る。
(数学オリンピックでの問題は8枚のコインでの裏向きコインの枚数の期待値でした。)
*熟読玩味ぃ〜^^;
|