何枚かのコインがすべて表向きに横一列で並んでいる。次の条件を満たす表向きのコイン
を無作為に一枚選んで裏返す。
(表向きコインは何枚も存在するも、選ぶ行為はランダムとする。条件を満たせば裏返せる。)
条件:そのコインより右に裏向きコインが一枚もないか、そのコインより左に裏向きコインが
一枚もない。
(両端のコインは隣が裏向きでも選ばれればひっくり返し可能)
条件を満たす表向きのコインが無くなるまでこの操作を続ける。
さて、操作が終了したとき、裏向きになったコインが10枚以上を期待するためには、最初
のコインは何枚以上を並べて置くことが必要になるでしょうか?
(コメント) 素朴に考えて、10枚のコインをすべて表向きに横一列で並べて、端から順次裏
返す、で出来ますが、「表向きのコインを無作為に一枚選ぶ」というところが難しい
ところですね!
らすかるさんからのコメントです。(平成30年1月8日付け)
計算がよくわからず、シミュレーションしてみたのですが、平均で裏向きn枚を超えるため
に必要な枚数は、
[e^((n+1)/2-γ)+1/2]
になるっぽいですね。ここで、γはオイラー定数≒0.577215665、[ ]はガウス記号
この式で、n=10とすると、137枚になり、他の適当に試したnでもシミュレーション結果と一
致しました。(参考→「A226161」)
DD++さんからのコメントです。(平成30年1月8日付け)
k 番目が裏返される確率は、 1/k + 1/(n+1-k) - 1/n なので、n枚のときに裏になる枚数
の期待値は、H[n] を調和級数として、
Σ { 1/k + 1/(n+1-k) - 1/n} = 2H[n] - 1
よって、 2H[n] - 1 ≧ 10 つまり、 H[n] ≧ 11/2 を解けばいいですね。
ここからは手計算じゃ無理ですが、n≒e^(11/2-γ) くらい。
GAI さんからのコメントです。(平成30年1月8日付け)
モンテカルロシミュレーションで、この結果を出されていることに驚きました。また、極限に
おける数式まで推測されていることに論理とプログラム力に改めて感服します。
数学オリンピック予選での問題にヒントを得て、改変して作問しておりました。その考え方
に感心したことが動機でした。
一般に、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枚のコインでの裏向きコインの枚数の期待値でした。)