テレビ朝日系列のバラエティ番組お試しかっ!のコーナー,「帰れま10」(かえれまてん)で,大体何皿食べないといけないのか,数学的に計算してみた.

簡単に終わるかと思ったが,思いの外難航し,2年以上悩まされることに.

&mimetex(E=\sum_{k=1}^{n+m}p\(k\)k);

#書き途中です

概要

テレビ朝日バラエティー番組「お試しかっ! 」内のコーナー「全て当てるまで帰れま10(テン)」
タカトシを含め6人の芸人でロケ先の店舗の人気メニュー上位10品を予想しながら注文する。 &note{wiki-kaerema10-refer:Wikipediaより引用,一部略};

これを数学的に解析しよう.果たして,当てるためには大体どれぐらい注文をしないといけないのか.まずはルールをちゃんと定義

番組ではn=10,mはロケを敢行するお店によりけりだが,ここでは一般化して,nとmで表す.例えば11月23日のSPはカラオケBIG ECHOで行われ,全97品の中から上位10品を注文するので,m=87,n=10の場合である.

n=1の場合(最も簡単なパターン)

まずは,最も簡単なm=1,n=1の場合を考えよう.つまりあたりもはずれも1個ずつの場合,起こりうる事象(事態)は次のうち2つ.

それぞれの事象が起こる確率は50%ずつなので,

#mimetex(E=1 \times \frac{1}{2}+2\times \frac{1}{2}=1.5)

で1.5回が期待値になる.ここでEが期待値を表し,大体どれぐらいの皿を注文すれば目標にたどり着けるか,を表す目安となる.

n=1における一般化

n=1の場合,問題は言い換えると,「何回目にあたりを引くか」にかかっている. そして,各事象(あたりを引くこと)は等確率である. よって,n=1の場合,食べる皿の期待値は以下のように求められる.

#mimetex(E=\sum_{k=1}^{m+1}k\frac{1}{m+1}=\frac{1}{m+1}\cdot \frac{1}{2}(m+1)(m+2)=\frac{1}{2}(m+2))

#mimetex(=\frac{1}{2}m+1)

が,問題はn=10のときなので,あんまり意味が無い.

一般化する前に

一般化する前に,下記の図で考える.下記の図はn=1,m=3の状態を表し,左下がスタートで,あたりを引くことで図の上方向に,はずれを引くことで図の右方向に移動する状態である. ゴールは最上部に到達することであり,到達方法によって試行回数が変わってくる.

図1.png

各頂点に到達する経路は1通りずつしかなく,よって終了する方法も1通りずつ,等確率である.

n1m3.png

こう考えると,帰れま10における試行回数は,前述の図で表した経路図において,
最上部まで到達するのに,何回頂点間を移動すれば良いか,と言う問題に置き換えられる.この経路図は,高さがn,幅がmの経路図になり,最上部の頂点間同士は横のつながりを持っていないという特徴がある.

n=2の場合

n=2の場合,経路図を描くと下記の様になる.(m=3,n=2の場合)

n2m3.png

注目すべき点は,以下の2点である.

この時の期待値Eは

#mimetex(E=\sum_{k=2}^{m+2}p\(k\)k=\frac{1}{10}2+\frac{2}{10}3+\frac{3}{10}4+\frac{4}{10}5=\frac{2+6+12+20}{10}=4);

となり,ゴールするための期待値は4回(食)ということになる.
この式を括ると,

#mimetex(E=\frac{1}{10}2+\frac{2}{10}3+\frac{3}{10}4+\frac{4}{10}5=\frac{1}{10}(1\cdot 2 + 2\cdot 3 + 3\cdot 4+4\cdot 5)=4); となり,

((ステップ数×経路数)の和)÷経路の総数

となる.

n=2における一般化

経路の総数をMで表すと,Mは1からm+1までの総和なので以下の式で表せる.

#mimetex(M=\frac{(m+1)(m+2)}{2}); 各ゴールの経路数とステップ数はそれぞれ2からm+2まで,1からm+1までの数列なので,以下の式で積を表せる(ただしkがステップ数でk-1が経路数)

#mimetex(k\cdot (k-1)); 以下の式

((ステップ数×経路数)の和)÷経路の総数

をmを使って一般化すると,以下のようになる

#mimetex(E=\frac{1}{M}\sum_{k=2}^{m+2}k\cdot(k-1)=\frac{2}{(m+1)(m+2)}\sum_{k=2}^{m+2}k\cdot(k-1)); さらに式を展開する

#mimetex(E=\frac{1}{M}\sum_{k=2}^{m+2}k\cdot(k-1)\\=\frac{2}{(m+1)(m+2)}\sum_{k=2}^{m+2}k^2-k=\frac{2}{(m+1)(m+2)}(\sum_{k=2}^{m+2}k^2-\sum_{k=2}^{m+2}k)\\=\frac{2}{(m+1)(m+2)}*1); &mimetex(\Sigma);内のkの式を展開し,総和を求める区間によって式を分けた.数列の和の公式から&mimetex(\Sigma);を展開してkを消去すると

#mimetex(E=\frac{2}{(m+1)(m+2)}*2\\=\frac{2}{(m+1)(m+2)}(\frac{1}{6}(m+2)(m+3)(2m+5)-\frac{1}{2}(m+2)(m+3))); となる.分子分母それぞれ3倍して後ろの項を整理し,共通項で括ると

#mimetex(=\frac{1}{3(m+1)(m+2)}*3\\=\frac{(m+2)(m+3)(2m+2)}{3(m+1)(m+2)}=\frac{2(m+2)(m+3)(m+1)}{3(m+1)(m+2)}=\frac{2(m+3)}{3}\\E=\frac{2(m+3)}{3}=\frac{2m}{3}+2); となる.

実際にm=3,n=2の場合に当てはめると,&mimetex(E=\frac{2m}{3}+2=\frac{2\cdot 3}{3}+2=2+2=4); となり,先ほど計算した期待値とも合致する.

一般化

とりあえずここまでわかってる結果をまとめると

&mimetex(n=1);&mimetex(\frac{1}{2}m+1);
&mimetex(n=2);&mimetex(\frac{2}{3}m+2);

なので,おそらく

#mimetex(E=\frac{n}{n+1}m + n);

ということが言えそうである.

というわけで,期待値の一般式を求めてみる.
基本的には,

#mimetex(E=\sum_{k=n}^{n+m}p\(k\)k);

である.総和の区間が&mimetex([n,n+m]);なのは,図からも分かる通り,最低でも当たりの食品を全て選択する,つまりn食食べる場合が最小で,最悪の場合すべてのハズレを選択してから当たりを選択する,つまりn+m食食べる場合が最大である.
それらの可能性&mimetex(p(k));と試行回数の積和で期待値が求まる.

general-nm.png

さてこの&mimetex(p(k));がクセモノであるが,冷静に観察してみると,特徴が浮かんでくる.
上にも示した図を,広く書いてると,2つの特徴が見えてくる.

一つ目は,nを固定した場合の数列,つまり各頂点での数字は右に見ていくと&mimetex({}_{n+m} \mathrm{C}_{n});になっていることが分かる.
当たりをa枚,ハズレをb枚食べる組み合わせは&mimetex({}_{a+b} \mathrm{C}_{a});で表されるので,確かに理にかなっている.

二つ目は,その総和が&mimetex({}_{n+m+1} \mathrm{C}_{n+1});,つまり座標で一つ上の場所の数字になっていることが分かる. これも,数列の総和で一つ上の数列が表されているので,自明なので証明は割愛.詳しくは三角数参照.

さて,実際の問題場合は,「ハズレを食べて終了」ということは起こらず,必ず正解を食べて終了となるので,各頂点への経路数は&mimetex({}_{n+m-1}\mathrm{C}_{n-1});で表され,その総和は&mimetex({}_{n+m}\mathrm{C}_{n});で表されることになる.
よって確率&mimetex(p(k));は以下のように展開でき

#mimetex(p(k)=\frac{{}_{k-1}\mathrm{C}_{n-1}}{{}_{n+m}\mathrm{C}_{n}});

期待値Eは以下のように展開できる.

#mimetex(E=\sum_{k=n}^{n+m}p\(k\)k\\=\sum_{k=n}^{n+m}\frac{{}_{k-1}\mathrm{C}_{n-1}}{{}_{n+m}\mathrm{C}_{n}}\cdot k);

ここで,組み合わせ&mimetex({}_a \mathrm{C}_b = \frac{a!}{(a-b)!b!}); と展開できるので,更に展開して整理する.

#mimetex(E=\sum_{k=n}^{n+m}\frac{{}_{k-1}\mathrm{C}_{n-1}}{{}_{n+m}\mathrm{C}_{n}}\cdot k\\=\sum_{k=n}^{n+m}\frac{m!n!}{(n+m)!}\frac{(k-1)!}{(n-1)!(k-n)!}\cdot k\\=\frac{m!n!}{(n+m)!}\sum_{k=n}^{n+m}\frac{(k-1)!}{(n-1)!(k-n)!}\cdot k\\=\frac{m!n!}{(n+m)!}\frac{1}{(n-1)!}\sum_{k=n}^{n+m}\frac{(k-1)!}{(k-n)!}\cdot k);

展開して得られた項のうち,kを含まない形の項を&mimetex(\Sigma);の左側にくくりだした.ここで,&mimetex((k-1)!k=k!);であり,&mimetex(\frac{k!}{(k-n)!}={}_k \mathrm{P}_n);であるので,以下のように数式を展開できる.

#mimetex(E=\frac{m!n!}{(n+m)!}\frac{1}{(n-1)!}\sum_{k=n}^{n+m}\frac{(k-1)!}{(k-n)!}\cdot k\\=\frac{m!n!}{(n+m)!}\frac{1}{(n-1)!}\sum_{k=n}^{n+m}\frac{k!}{(k-n)!}\\=\frac{m!n!}{(n+m)!}\frac{1}{(n-1)!}\sum_{k=n}^{n+m}{}_k\mathrm{P}_n);

さて,ここで行き詰まった.&mimetex(\sum_{k=n}^{n+m}{}_k\mathrm{P}_n);がどうにも解けない.ただし,幾つか手で解いて見たところ,おそらく

#mimetex(\sum_{k=1}^{a}{}_k \mathrm{P}_b=\frac{1}{(b+1)}\overbrace{(a+1)a(a-1)\cdots(a+1-b)}^{b+1});

が成り立つっぽい.ここでは成り立つとして,式に当てはめる.

#mimetex(E=\frac{m!n!}{(n+m)!}\frac{1}{(n-1)!}\sum_{k=n}^{n+m}{}_k\mathrm{P}_n\\=\frac{m!n!}{(n+m)!}\frac{1}{(n-1)!}(\sum_{k=1}^{n+m}{}_k\mathrm{P}_n-\sum_{k=1}^{n-1}{}_k\mathrm{P}_n)\\=\frac{m!n!}{(n+m)!}\frac{1}{(n-1)!}(\frac{1}{(n+1)}(n+m+1)(n+m)\cdots(m+1)-\frac{1}{(n+1)}n(n-1)\cdots(n-n))\\=\frac{m!n!}{(n+m)!}\frac{1}{(n-1)!}\frac{1}{(n+1)}\frac{(n+m+1)!}{m!}\\=\frac{m!n!}{(n-1)!m!}\frac{(n+m+1)!}{(n+m)!}\frac{1}{(n+1)}\\=\frac{n(n+m+1)}{(n+1)}=\frac{nm}{(n+1)}+\frac{n(n+1)}{(n+1)}=\frac{n}{n+1}m+n);

途中で&mimetex(\frac{1}{(n+1)}n(n-1)\cdots(n-n));の項を消去しているが,&mimetex((n-n)=0);なのでこの項は0になる. よって,食べる食事の期待値は,当たりをn種類,ハズレをm種類としたときに

#mimetex(E=\frac{n}{n+1}m + n);

によって表される. 残るところは&mimetex(\sum_{k=1}^{a}{}_k \mathrm{P}_b=\frac{1}{(b+1)}\overbrace{(a+1)a(a-1)\cdots(a+1-b)}^{b+1});の証明だけだが,とりあえずここまででおしまい..

案外キレイな形にまとまったものである. 帰れま10ではn=10なので,

#mimetex(E=\frac{10}{11}m + 10);

ちなみに,過去の放送回から計算される期待値と実際にロケでかかった食事の回数を表にすると,以下の通り.

放送回品数mn期待値食事回数
22100901091.8222
3492821084.5531
3613312310121.8230
4711610610106.3631
49106961097.2730
5384741077.2735
68102921093.6429
7675651069.0933
8197871089.0942

ランダムで選択してるといつまで経っても終わらない(ゆうに100回を超える試行が必要)だが,実際は30回程度の選択で終わっている. こう見ると,悩んで選択してるのが如何に有用かが分かる.

参考

パーフェクトを実際達成

ジャンル:数学


*1 \sum_{k=1}^{m+2}k^2-\sum_{k=1}^{1}k^2)-(\sum_{k=1}^{m+2}k-\sum_{k=1}^{1}k
*2 \frac{1}{6}(m+2)(m+3)(2m+5)-1)-(\frac{1}{2}(m+2)(m+3)-1
*3 m+2)(m+3)(2m+5)-3(m+2)(m+3

添付ファイル: filegeneral-nm.png 1158件 [詳細] file図1.png 1944件 [詳細] filen1m3.png 2008件 [詳細] filen2m3.png 1970件 [詳細]

トップ   編集 凍結 差分 履歴 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2020-10-22 (木) 09:01:37