先日出した問題(id:Nabetani:20060109:p1)に「領域二分割があれしてごめんなさい私のネーミングセンスが無さ過ぎてまともな名前が思いつきません問題」というタイトルをつけたいただいたんだが、長すぎて不便なので「領44ん問題*1」とここでは省略させていただく。
で。
n=4 の場合について考えてみたんだが、人間が数えるのはかなりしんどい感じである。
今のところ、80〜100 ぐらいという感じだが、数え漏らしと重複がないと確信できるような数え方をまだ思いついていないのではっきりしない。
そのうち領44ん問題を解くプログラムを書こうと思ってるんだが、今週末はとりあえず無理。いつになることやら。
なんて言っているうちに忘れそう。
で。
それとは別に問題。
1以上S以下の整数値を取る一様な乱数を n個発行する。
このとき、一度しか出なかった値が何個あるか数え、その個数を g とする。
gの期待値を最大とするような n を S で表せ。
つまり。ニコリダービーでゴールインできる人が一番多くなるのは投稿者が何人の時か。というような感じの問題。
出走枠が 1個なら：
- n=1 なら、E(g)=1。
- それ以外は E(g)=0。
簡単。
出走枠が 2個なら：
- n=1 なら、E(g)=1。
- n=2 なら、E(g)=(1/2)×2 + (1/2)×0 = 1。
- n=3 では g≦1 なので、E(g)＜1。
というわけで、N=1, N=2 の時に最大値となり、E(g)=1。
まあまあ簡単。
では、出走枠が100個 ならどうだろう。
という問題を先日思いつき、寝ながら考えていたときは手も足も出ず。電車の中で真面目に考えたら解けた。
