44種類のポスターを揃えるには何枚買う必要があるか（1）

http://blog.livedoor.jp/dqnplus/archives/1097052.html
経由
http://ameblo.jp/akihabara48/entry-10075346906.html

これは面白い。
いや、他人事だからだろうけど。
プログラミングのネタとして面白い。
ランダムでポスターを買って、何枚買うと44種類が全部揃うだろうか。
（実際には、44枚セットを買えばいいという話に変わったらしい）

組合せ論を使えば厳密にもできるだろうが、
とりあえず、擬似乱数で100万回やってみたら、
こんな確率分布が出た。
そんなに間違っていないと思う。

平均192枚買って全部揃う。
最小71枚、最大880枚。

use strict;
my $nMembers = 44;      # must be even

my $half = $nMembers / 2;

my $full = (1 << $half) - 1;

my $nPlay = 1000000;

my @freq;
my $sum = 0;

for(my $i = 0; $i < $nPlay; $i++) {

    my $n = play();

    $freq[$n]++;

    $sum += $n;

}
for(my $i = $nMembers; $i <= $#freq; $i++) {

    printf "%4d %f\n", $i, $freq[$i] / $nPlay;

}
printf "mean : %.2f\n", $sum / $nPlay;
sub play {

    my $n;

    my ($lower, $upper) = (0, 0);

    for($n = 0; ($lower & $upper) != $full; $n++) {

        my $r = int(rand() * $nMembers);

        if($r < $half) {

            $lower |= 1 << $r;

        }

        else {

            $upper |= 1 << ($r - $half);

        }

    }

    

    return $n;

}