食玩問題


背景

先日、福岡市美術館では大英博物館至宝展なるものがありました。そ この売店には全部で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 箱買って全15種類揃う確率 = 1 - 15 * (14/15)^n

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

n 箱買ってそろう確率 = 1 - n 箱買ってもそろわない確率 「あと1個がゲットできない」の「1個」の選びかたは15とおり。 その「1個」をはずしまくって 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で全種類手にはいるか。

そのうち知人の許可をもらってその考え方を載せたいと思い ます。えーと、もらいました。 ここに導出過程を置きます。


解析解から近似解が導出されることが示される

解析解が手にはいるとそれから近似解を導出できることが示されます。 意外と簡単でした。

ちなみに解析解と近似解の関係は次のようなグラフになります。


さらなる一般化へ

知人はこのころになるともう完全に「食玩問題」にはまりきっていて、 いくつか一般化した式を提出してきます。

つまり先ほどまではN個の欲しいおまけがあって、n箱買ったときにど のくらいの確率で全種類が手にはいるかという問題でした。

これを次のように一般化しました。N種類のおまけがあってすでにa種 類持っている。これからn箱買ったときに手元にm種類になる確率pを 求める式。

最後にはここまできました。N種類のおまけのうち、b種類欲しいのが ある。今、手元には、b種類のうち、a種類そろっている。これから n個のおかしを買い増ししたとき、手元に揃った種類数がmとなる確率 はどうなるか?(N>0,n>=0,N>=b>=m>=a>=0)

この問題についてもきちんとした解析解が示されました。

この問題のかなり一般的な解になっているでしょうね。


みんなが使えるようにしよう

ここで知人は完全に満足してしまいました。真理に近づくのは楽しい ものです。しかし工学ではやっぱりこの知見を利用してみんなが使え ないといけません。ということで、このまとめのページを作ったわけ なんです。

さきほどの学生さんにたのんでJava Scriptを組んでもらいました。

おまけの種類の数

これから欲しい数

これから買う数




手に入る確率

たとえば、おまけの種類の数15、これから欲しい数15、これから買 う数73を入力してもらうと手にはいる確率0.90556が出てきます。ち なみに買う数72では0.89906となりまして、90%をほんのちょっと切 ります。

あるいは、これまで5種類はすでに手に入れていて、最終的には8種 類が欲しいときには、「これから欲しい数」を8-5=3にして確率計算 することができます。

さあ、みなさんこのページを利用して、コンプリートするまでの確率 を計算して、おまけをゲットしてください!!

(注) もし結果が変なときには、後に 別な計 算方法を実装した計算機 計算機のページ がありますので、そちらを参照ください。


いろいろな情報

だいたい知人自身がこの問題を提出しているときに、自ら至宝展の売店 に行き理論武装の元で闘ってきました。73個とは350円*73=25550円に もなるのですが、次から次に買ってはその場で開け、愕然としたそうな。

結果は...5個買って2種類のみ手にいれました。;_;

食玩ではひどいめや天国にいる気分になった方は多いようで、そのリ ンクを教えてもらいました。

確率論を展開する人も多いようです。

店頭での商品シャッフル問題(アソート)は、「均等」ではなく「ランダム」の ようです。

ガチャポン・食玩の確率論

そうそう、現実には、公表されていない種類のおまけがあったり偏り があったりするので、なかなかコンプリートできないですよね。

どうしても欲しいけど、そんなにお金をかけるのには躊躇する、とい うのであれば、

その手の専門店

やオークションを使う手がありますね。


まとめ

このページをまとめようと思ったのは、やはり得られた知見をみんな の役に立つようにしないといけないという工学的な発想からです。 参考 ページ

また今回の、問題があってそれを解く過程が、本当に研究のやり方の典 型例だったからです。シミュレーションでまずとにかく答えを手にい れる。厳密解をもとめる。さらに効率を上げる。一般化する。みんな が使えるようにする。そういう意味もあってまとめました。何かの役 に立てば幸いです。


その後

このページはおかげさまで人気のページのようで、いろいろなとこ ろでリンクされて使われているようです。工学に携わっているもの としてはありがたいことです。いくつかメールをいただいたので記 録しておきます。

白夜書房というところから発行している隔月間の雑誌「ハッカージャ パン」の2010年1月号のコラムに取り上げていただきました。執筆さ れた神戸大学大学院工学研究科の森井昌克先生に感謝申し上げます。 (2009/12/22)

AKB48の「 ワンダフルルーレッ ト」という最近終わった販促キャンペーンの解析に使ったとい うメールをいただきました。これは73日間、毎日1回、56個の賞品 から1つをルーレットで抽選するというものです。ところが、抽選 結果では、68日目で、56個すべてが出揃いました。このページをご 覧の方は分かるように、思ったよりも確率は低いです。実際の値は とんでもなく低く2.31E-14です。(2011/5/18)

実は、上の2.31E-14というのは最初の学生さんが作ってくれた JavaScriptのプログラムでは計算することができません。解析解を 数値的に解いていくと、計算機では桁落ちが起きて数値的に扱えな くなるからです。このことについて知人に相談したら、なんと漸化 式を使う計算解を使う方法を提案してくれました。下にある JavaScriptでは56個のおまけがあって、56個欲しくて、68回試して みたという計算ができます。

この考え方も工学っぽくて興味深いです。数学的には解析解を出す ことが重要ですが、工学ではそれを使えるようにすることが重要で す。この場合には計算機の性能が限られているから、解析解を直接 数値にするよりも、数学的には美しくないかもしれないけど漸化式 から数値化していくということを行うことに工学的な意味がありま す。

普通の問題では解析解が一番数値計算するのが楽で、計算時間も計 算に必要なメモリも計算量(CPU)も小さいです。計算解は解析解より も計算コストが大きいので使われないです。しかし今回の問題では 計算解では計算のコストはややかかるはずですが、逆に実用上はこ ちらで解いた方がスムーズです。

こう考えていくと、場合によってはもっと後退して、近似解や思い つきの解(モデル解)なんていうのが実用的になる場合だってある はずです。(2011/6/1)

漸化式を利用して確率を計算するプログラム
おまけの種類の数

これから欲しい数

これから買う数




手に入る確率

「解析解」と「計算解」を両方比較してみたい方のために、 一つのページ にまとめました。お楽しみください。


小田部荘司のホームページに戻る