ダンジョンに宝箱がn個ある。
n種類のアイテムがそれぞれ重複せずに
ランダムに箱にセットされる。
プレーヤーは1回に1つの箱しか開けられない。
全ての箱で全てのアイテムが出現する場面を確認したい。
平均何回かかるか。
とにかく一つ一つ箱を調べていく。
n=3として、
最初の箱で、
アイテム1、アイテム2、アイテム3と出現すれば3回で済む。
が、そうなる確率は2/9で、もっと多くかかることが多い。
Perlで書くとこんな感じか。
my $n = 3;
my $m = 1000000;
my $total_count = 0;
my $flag_full = (1 << $n) - 1;
for(1..$m) {
my $flag = 0;
my $counter = 0;
do {
$flag |= 1 << int(rand()*$n);
$counter++;
} while($flag != $flag_full);
$total_count += $counter;
}print $total_count / $m, "\n";
平均5.5回らしい。
3倍して16.5回。
数学的に考える。
まず、最初のアイテムが見られるまでには1回。
1つアイテムが見られた状態で、
別のアイテムが見られる確率は2/3。
だから別のアイテムが見られるまでに平均3/2回。
同様に2つアイテムが見られた時点で、
最後のアイテムが見られる確率は1/3。
だから最後のアイテムが見られるまでに平均3回。
全部のアイテムが見られるまでにかかる平均回数は、
1+3/2+3=5.5回というわけ。
それを3倍して16.5回。
一般的には
n2(1+1/2+...+1/n)
ここまでは簡単。
この項つづく。
