大人数でじゃんけんをしたことはありますか。
人数が多いほどあいこになりやすく、勝敗が決まるまでに時間が掛かると定評のあるじゃんけんです。
そこで、こんな疑問が浮かびました。
問題
地球上の全人類で同時にじゃんけんしたら、終わるまでにどのぐらいかかるのか。
もちろん、トーナメントや総当たりではなく、輪っかになってやる、あのじゃんけんです。
勝者を一人決めるだけなら、トーナメント方式等を採用した方が効率的です。
ですが、大人数でやった方が楽しいはずです。
現実的な解答
地球上の人口は80億人だとします。どうにか参加してくれたとします。
その中には絶対、面倒だったり、理解してなかったりで
- 「グー」しか出さない人
- 「チョキ」しか出さない人
- 「パー」しか出さない人
の3人がいるので、「一生終わらない」。
――――
問題として面白くないので、みんな、等確率でグーチョキパーを出してくれることにします。
また、王者を1人に決めたいので、複数人が勝ったら、勝った人たちだけで残って、1人になるまでじゃんけんをすることにします。
すると、問題は次のようになります。
問題
N人が等確率で手を選んで一つのじゃんけんをする。負け抜けで勝者が1人に決まるまで繰り返すとして、(あいこも含めて)平均何回じゃんけんが行われることになるか。
一体どのぐらいになるのでしょうか。
「無限の猿定理」と呼ばれる話がありますが、猿がランダムにタイピングしてシェイクスピアの作品を打ち出すのと、全人類の同時じゃんけんが終わるのはどちらが早いでしょうか……。
はじめの問題
簡単な問題から考えていきます。
問1
N人のじゃんけんで、(あいこにならず)勝敗が付く確率はいくらか。
勝敗が付く場合は、「グーとチョキだけ」「チョキとパーだけ」「パーとグーだけ」の3つに分割できます。
そして、たとえば、グーとチョキだけで勝敗が付く確率は、
- (グーとチョキだけで勝敗が付く確率)=(パーが1人も出ない確率)ー(全員グーの確率)ー(全員チョキの確率)
で計算できます。
○○の確率を、と書くことにすると、
です。よって、
となります。チョキとパーや、パーとグーの場合も同じです。したがって、3倍して、
と分かります。
答1
最初の勝敗までの試行回数
次は、今出した答えから、最初に勝敗が付くまでの平均何回を求めます。
問2
N人のじゃんけんで、最初の勝敗が付くまでに(あいこも含めて)平均何回のじゃんけんが行われるか。
確率pの事象が起きるまでの平均試行回数は、1/pであるという公式から、逆数をとればいいです。
答2
平均回行われる。()
試しに代入して計算する
試しに計算してみたいですよね。私はしたいです。
N=8000000000で計算すればいいわけですが、そのままコンピュータで計算しようとすると、計算量が多すぎて(時間が掛かりすぎて)計算できません。
ですが、大丈夫。対数()を使うと、指数部分を簡単なかけ算で計算できます。なぜなら、ある計算したい値について、ならば、だからです。
N=8000000000で計算すると、1回勝敗が付くまでの平均試行回数をMとしたとき、
\begin{equation} \\ M = \dfrac{3^{8000000000-1}}{2^{8000000000}-2} =9.297\cdots \times 10^{1408730071} \end{equation}
でした。計算方法によって誤差は変わってきます。
1那由他や1不可思議が、やのレベルなので、次元が違います。とにかくヤバいってことです。
さらにこれは、最初の1回目の勝敗が付くまでなので、No.1の王者を決めるためにはもう少しかかることになります。
No.1を決めるまで
問3
N人のじゃんけんで勝敗が付いたときに、勝者がW人である確率はいくらか。
条件付き確率と言われるやつです。
たとえば、W=1、つまり勝者が1人だけ出る確率を考えてみます。この確率を出すためには、「勝者が1人出る組合せの数」を「勝者が出るすべて組合せの数」で割ればよいです。
「勝者が1人出る組合せの数」というのは、番号1の人が勝ち、番号2の人が勝ち、......、番号Nの人が勝ち、のNパターンがあります。また、勝った手が「グー」「チョキ」「パー」の3種類あるので、3×Nです。
対して、「勝者が出るすべての組合せの数」は、勝者が出た(あいこでない)とき、それぞれの番号の人が「勝つ手」か「負ける手」を出しているので、(全員が同じ手のあいこの2パターンを除いて)、パターン。「勝つ手」がやはり、「グー」「チョキ」「パー」の3種類で、パターン。
よって、勝敗が付いたときに勝者が1人の確率は、
です。
勝者が2人の場合はどうでしょうか。「番号1と2の人が勝ち」「番号1と3の人が勝ち」……「番号1とNの人が勝ち」のN-1通りのケースの他に、「番号2と3の人が勝ち」「番号3と7ノ人が勝ち」のようなケースもあります。要するに、N人から2人選ぶ組合せの数です。
一般の勝者W人について、数学では、このような組合せの数を、と表記します。
そして、数学の公式から、たとえばW=4のとき、この値はのように計算できます。
ゆえに、一般の勝者Wについて、
です。
答3
本題
ついに本題を解くことができます。
問4
N人が等確率で手を選んで一つのじゃんけんをする。負け抜けで勝者が1人に決まるまで繰り返すとして、(あいこも含めて)平均何回じゃんけんが行われることになるか。
n人で勝者を1人に決めるまでの、平均じゃんけん回数をとします。n人で1回勝敗が付くまでの平均試行回数を、n人で勝敗が付いたときに勝者がw人である確率をとします。
とは、問2と問3で求めたものです。
このとき、
です。まず、勝敗が付くまでじゃんけんをしたあと、それぞれの確率で、残った人数での場合の回数をさらに足すという意味です。
これまでで導いた式を代入して、
\begin{equation} \\ T_n=\dfrac{3^{n-1}}{2^n-2}+\sum_{k=2}^{n-1} {}_n \mathrm{C}_k \dfrac{1}{2^n-2} T_k. \end{equation}
を得ます。の関係ない因子(積の要素)は外側に出すことができるので、
\begin{equation} \\ T_n=\dfrac{3^{n-1}}{2^n-2}+\dfrac{1}{2^n-2} \sum_{k=2}^{n-1} {}_n \mathrm{C}_k \cdot T_k. \end{equation}
となります。
n=2が初項の、一種の漸化式となりました。うまくやれば解けそうですが、ひとまず、これで答えとしておきます。
答4
平均回。ただし、について、\begin{equation} \\ T_n=\dfrac{3^{n-1}}{2^n-2}+\dfrac{1}{2^n-2} \sum_{k=2}^{n-1} {}_n \mathrm{C}_k \cdot T_k\ . \end{equation}
直接計算する代わりに
漸化式にはなったので、あとはN=8000000000で計算するだけですが、そこらのコンピュータでは、計算量やメモリの問題で計算が困難です。
ですが、大丈夫です。下界と上界なら求めることができます。つまり、おおよその値の範囲なら分かるということです。
(今回の場合、下界は、少なくとも何回はかかる、という目安。上界は、少なくとも何回内には終わる、という目安。)
(ちなみに、上界に似た用語に「上限」がありますが、上界の中で最善のものを上限と言います。たとえば、「サイコロの出る目の上界」は6でも8で100でもいいですが、「サイコロの出る目の上限」は6のみです。下界についても同様。)
下界と上界
問5
の下界と上界を与えよ。
下界から求めます。少なくとも、最初のN人の時に勝敗が付く必要があるので、問2の答えであるが下界として使えます。
あいこにならず最初の1回で勝敗が付くことも勿論ありますが、今考えているのは平均回数の下界です。
上界を考えます。明らかにについてです。勝者が1人に決まるまでに、じゃんけんで脱落者が出るのは、高々N-1回です。
つまり、勝敗が出るまでのじゃんけんを高々N-1回すればよく、それぞれで勝敗が出るまでの平均回数はN人の時の平均回数:以下なので、を上界として使えます(かなり大雑把な上界です)。
答5
下界はで、上界は。要するに、\begin{equation} \\ \dfrac{3^{N-1}}{2^N-2} \le T_N \le (N-1)\dfrac{3^{N-1}}{2^N-2} \ .\end{equation}
やっと計算
この不等式を、問2の後で計算した結果を借りて、N=8000000000で計算してみると、
\begin{equation} \\ 9.297\cdots \times 10^{1408730071} \le T_N \le 7.437\cdots \times 10^{1408730081} \end{equation}
となります。より簡単に書けば、
\begin{equation} \\ 10^{1408730071} \le T_N \le 10^{1408730082} \end{equation}
です。
やっと求まりました。
結論
全人類80億人で負け抜けのじゃんけんをした場合、(あいこも1回に数えて)終わるまでに平均回じゃんけんをする必要がある。
∎
ちなみに
ちなみに、先ほどの勝者が1人に決まるまでのじゃんけんの平均回数ですが、小さいnでなら厳密な値を計算できます。
そのグラフが以下になります。ほぼ指数関数に一致しています。
logを取ると見事に直線になります。
Excelで出た指数近似の式は、人数xが大きくなるほど、真の値との相対誤差が小さくなります。問5で求めた下界と上界の式はどちらも巨視的に指数関数だったので納得できる結果です。
この式を使っても、およそのを得ることができます。実際にx=8000000000を代入して計算すると、となります。10の指数部を下界と比較すると、です。下界よりも小さく出てしまいましたが、この差を大きく見るか小さく見るかは人それぞれでしょう。
ともかく、およそのを知りたいときは、問5の下界と上界の式を使った方がいいです。
少しだけについて考察しておくと、1区切りの勝敗が付いたとき、統計的に残る人数は大体半分になります(正規分布と同じです)。1区切りの勝敗が付くまでの平均回数は指数的に増加するので、元々の人数のときに比べたら、半分の人数で勝敗が付くまでの平均回数は(Nが大きいとき)非常に小さなものです。
なので、負け抜けで最後までやるとしても、最初のN人で1回勝敗が付いたら終わりでも、平均回数はあまり変わらないことになります。これが、の下界と上界がN倍ぐらいしか違わない理由です。
無限の猿とどちらが長い
では、冒頭のもう一つの疑問も検証してみましょう。
「無限の猿定理」と呼ばれる定理があります。猿がランダムにタイピングすることで、いつかはシェイクスピアの作品を打出すというものです。
さて、全人類がじゃんけんし終わるのと、猿がシェイクスピアの作品を打つのと、どっちが早いでしょうか。
この記事によると、シェイクスピアの有名な作品である「ハムレット」は、英語で約20万字のようです。
キーボードで打てる文字種を大文字なども入れて100種とします。猿はいずれかの文字を等確率(1/100)で、1秒間に10打つとします。
間違えるときには、1文字目で間違えることもあれば、55文字目で間違えることもありますが、間違えるまでの平均打数は多く見積もって2とします。
すると、猿が長さLの特定の文字列を打ちだすまでの平均打数は、
です。L=200000のとき、
ですから、かかる平均時間は
です。
仮に人類側が1秒間に1回じゃんけんができたとしても、その決着がつく前に、猿は以上のハムレットを打ちだすことができます。
多分、猿が進化してシェイクスピアを理解する方が早いです。そんなこと言うなら、人間が正気に戻る方が早いです。
まとめ
- じゃんけんの参加人数が1人増えると、決着がつくまでに掛かる時間は大体3/2倍になる。
- 80億人でじゃんけんをすると最初の勝敗が付くまでに、平均で約回あいこになる。
- 勝者を1人に絞り込むまでのじゃんけんの回数も、同じぐらい。
- 全人類がじゃんけんしている間に、1匹の猿はランダムにタイピングして無数に文学作品の複製を打ちだせる。
ありがとうございました。