食玩問題

背景

先日、福岡市美術館では大英博物館至宝展なるものがありました。そこの売店には全部で15種類のおまけがついているクッキーが売っておりました。箱の中には一つのおまけとクッキーと入っているわけですね。もちろんクッキーが目的でなくてこのおまけ(食玩)が欲しくて買うわけです。

知人はそこで次のような問題を出しました。

「確率90%以上で全15種類を手にいれたいとき、何個買ったらよいでしょう？」

これについて、まとめることにします。

シミュレーションで答えを出そう

ちょっと考えてみると、次のように考え付きました。15個買って全部違う種類になって成功する確率は... 15!/15^15だ。16個買って15個揃う確率はうーん、15!/15^15*(15/15+14/15+13/15+12/15+ ... 1/15)だろう。ということはこれを漸化式っぽく書いていけばn個の時もとけるだろう。しかし、大変そうだ。

そこで学生さんに相談して解いてもらうことにしました。彼は早速 シミュレーションをしてくれました。そうそう、問題を解くときにはシミュレーションはいいですよね。つまりこうです。箱を n個買います。その中にはランダムで15種類のおまけが入っています。箱を開けておまけをチェックして15種類全部あるか無いか調べます。これを1000回、10000回くらいやって成功する回数と失敗する回数から成功確率を求めます。

簡単なプログラムで彼は「72個じゃないですか」と答えを出してくれました。私も別にプログラムを組んで 73個が正解 ではないかという答えを出しました。

近似解が提出される

知人にこの結果をお知らせすると、nが大きいときに成り立つだろうと思われる近似解を示してきました。

知人が夜に「ふと思いついた式」というのは、

n 箱買って全１５種類揃う確率 = 1 - 15 * (14/15)^n

でした。この式の考え方は、

n 箱買ってそろう確率 = 1 - n 箱買ってもそろわない確率「あと１個がゲットできない」の「１個」の選びかたは１５とおり。その「１個」をはずしまくって n 個買う確率 = (14/15)^n

というものでした。

で、確かにこれで計算すると73個という答えが出てくるのですが、近似式なので、nが小さくなるとだめで、40個とかだと破綻してきます。さて次はどうするか。

大人買いと子供買い

外野では一度にまとめて買うのか、一個づつ買って確かめながらやるのか、というような話題になっておりました。

大人買い：一度にまるごと、つまり段ボールに箱がたくさん入っている状態で全部買込んで、やおら開けていく。

子供買い：一つ買っては開けて、また一つ買っては開けて、揃うまで頑張る。

これらって同じでしょうか。違うのでしょうか。同じだという意見では大人買いしたところで、やっぱり一個一個開けていき、コンプリートしたところで、オークションで売ってしまうから(笑)、ということでした。

子供買いの時には、開けていってコンプリートしたところで買いませんから、若干問題が異なっています。今回の解こうとしている問題の場合には、きちんと言えば大人買いをした時に、ほしいおまけが揃っているかということになります。たとえば16個買って開けていって 15個開けたところで仮に全種類揃ったとしても、次の1個を開けるという行為を入れて確率を計算しています。つまり16個買ったとして、 15個開けたところで揃う確率+16個目を開けて揃う確率が、16個開けて揃う確率になっています。

きちんとした漸化式の提案およびその解

学生さんはきちんと考えてくれる性格で、数日してから漸化式を提案してくれ、さらにプログラムも出してくれました。かなりエレガントできちんとしております。

おまけの種類 n種類 
すでに手にいれている種類 m種類(＜n)
残りの開けていない箱の数 l個

として、全種類ゲットできる確率fは

n-m>l -> f=0
n-m=0 -> f=1

f(n,m,l)= (n-m)/n*f(n,m+1,l-1) + m/n*f(n,m,l-1)

           当たときの確率      +  はずした時の確率

これを解く、プログラムは以下の通りです。


#include 

#define N 15
#define L 100

double Data[N+1][N+1][L+1];

double f(int n,int m,int l)
{
	if(Data[n][m][l]>=0)return Data[n][m][l];
	if(n-m>l)return 0;
	if(n==m)return 1;
	
	Data[n][m][l]=(double)(f(n,m+1,l-1)*(n-m)/n+f(n,m,l-1)*m/n);
	return Data[n][m][l];
}

int main()
{
	int i,j,k;
	int l;
	for(i=0;i<=N;i++)for(j=0;j<=N;j++)for(k=0;k<=L;k++)
		Data[i][j][k]=-1;
	for(l=15;l<=L;l++){
		printf("%2d %2d %f\n",N,l,f(N,0,l));
	}
	
	return 0;
}

私も、最初に思いついた自分の漸化式を解くプログラムを使って、学生さんと同じ結果が出ることを確認しました。これで一応きちんとした解析解を得ることができるようになりました。さて、こうなるとこんなプログラムを使わなくても解析解が出る式が欲しくなってきますね。

初めての解析解発表

ここからが問題が難しくなってきます。知人は先ほどのプログラムを改良しつつ、解析解を出してきました。この解析解を出すのは結構大変で、行列を利用して対角化をしてn個の場合に拡張してとややこしいです。とにかくその結果は次の通りです。N種類の欲しいおまけが n箱買ったときにどのくらいの確率pで全種類手にはいるか。