大人数で効率よくじゃんけんをする方法を検証した

こんにちは、数学好きと言いつつ数Aの「場合の数と確率」が苦手な108Hassiumです。

先日、こんなツイートを目にしました。

数年前に開発した、5人以上でジャンケンしてもほぼ１発で勝負が決まる１発ジャンケンを記録として残しておきます。#１発じゃんけん pic.twitter.com/sxMSRka95e
— 三日月マンハッタン仲嶺 (@mikadukinakami) 2020年2月22日

ザ・ボッツェスト(ボッチの最上級)である私には大人数でじゃんけんをする機会はほとんどありませんが、数学好きとしてちょっと興味が湧きました。

というわけで、大人数で効率よくじゃんけんをする方法を検証しました。

検証方針

「1発じゃんけん」と「普通のじゃんけん」、その他いくつかの方式について、以下の項目により効率を評価します。

即決確率：1発で一人勝ちが起こる確率です。

人数減少率：1回の試行で人数がどのくらい減るのかを表す数値です。

長所・短所：上記の2項目以外に特筆すべき性質があれば書きます。

なお、この記事には大量の数式が含まれますが、「適当に拾い読みすれば、中学生レベルの知識で理解できる」程度の内容になるように書いているつもりです。

興味がない人は、数式は読み飛ばしてください。

通常式

まず、普通のじゃんけんから検証します。

検証方法の説明も兼ねているので、計算方法を少しだけ詳しく説明します。

即決確率 $=\frac{n}{3^{n-1}}$

※ $n$ は人数

手の出し方は全部で $3^n$ 通りあって、その内の一人勝ちのパターンは

・勝つ人が $n$ 通り
・手の出し方が3通り

なので、一人勝ちの確率は $\frac{3n}{3^n}=\frac{n}{3^{n-1}}$ となります。

人数が増えると一発一人勝ちは発生しにくくなることが分かります。

人数減少率 $=1-\frac{2^{n-1}-1}{3^{n-1}}$

人数減少率は、「『勝ち残り人数の期待値』を人数で割った値」と定義します。

「期待値」というのは、大雑把に説明すると「どんな結果が起こりやすいか」を表す値で、「結果を表す値」×「その結果が起きる確率」の値を全部足したものになります。

例として、「コイントスで表が出たら100円もらえて、裏が出たら10円取られる」というゲームを考えます。

このゲームの賞金の期待値は、 $100×\frac{1}{2}+(-10)×\frac{1}{2}=45$ 円になります。

この値が何を意味するかというと、例えば「サイコロで1が出たら10円もらえて、1以外が出たら2000円取られる」というゲーム(期待値は-1665円)と比較して「サイコロのやつよりコイントスのやつの方が期待値が高いから、コイントスの方に参加しよう」と判断するのに使えます。

さて、じゃんけんの話に戻ります。

$n$ 人でじゃんけんをしたときの勝ち残り人数は、 $1～n$ (あいこで $n$ 人残る場合を含む)の値をとり、それぞれの確率は異なります。

まず人数が減る場合の確率は、即決確率と同じように「勝つ人の組み合わせ数」×「手の出し方の数」÷「総パターン数」で求められます。

あいこで全員残る場合は人数が減る場合の余事象になるので、1-(「1人残る確率」+「2人残る確率」+「3人残る確率」+...「 $(n-1)$ 人残る確率」)と表せます。

以上より、人数減少率は以下の式で表せることが分かりました。

$\frac{1}{n}\left(\displaystyle\sum_{k=1}^{n-1}\frac{k _nC_k}{3^{n-1}}+n\left(1-\displaystyle\sum_{k=1}^{n-1}\frac{ _nC_k}{3^{n-1}}\right)\right)$

$\Sigma$ は足し算の繰り返しを表す記号で、「1人残る確率」+「2人残る確率」+「3人残る確率」+...「 $(n-1)$ 人残る確率」の部分に対応しています。(今後出てこないので、理解しなくても大丈夫です)

過程は省略しますが、これを頑張って計算すると $1-\frac{2^{n-1}-1}{3^{n-1}}$ になります。

数式だけ見せられてもピンとこないと思うので、グラフにしてみました。(横軸が $n$ )

f:id:Hassium277:20200308001209p:plain

$n$ が大きくなると、人数減少率は1に近づいていくのが分かります。

人数減少率が1に近づいていくという事は人数が減りにくくなるという事なので、「普通のじゃんけんは大人数でやると時間がかかる」という直観的に予想できる性質が数学的に立証されたことになります。

...ちなみになんで「残り1人になるまでの試行回数の期待値」とかの直観的に理解しやすい値にしないかというと、計算が面倒臭かったからです。

長所

・ルールが分かりやすい

一発じゃんけんのツイートでも指摘されていますが、新しいやり方には必ずそれを説明する手間が付いてきます。

その点通常式は説明不要なので、円滑に実行することができます。

短所

・特になし？

何も思いつきませんでした。

以上が通常式じゃんけんの分析結果です。

最初なので数式を駆使して詳しく説明しましたが、多分興味ない人が多いと思うのでここからは粗めの解説に切り替えます。

一発式

冒頭で紹介した一発じゃんけんです。

ルール

・1～5の数を出せる

・同じ数を出した人がいない参加者のうち、最大の数を出した参加者が勝ち

・どの数も2人以上出していた場合はあいこ

即決確率 $=\frac{5n×4^{n-1}-10n(n-1)×3^{n-2}+10n(n-1)(n-2)×2^{n-3}-5n(n-1)(n-2)(n-3)}{5^n}$

なんかめっちゃ長い式になりました。

グラフにするとこうなります。

f:id:Hassium277:20200304221448p:plain

当然ですが、やはり人数が増えると即決確率は下がるようです。

次は通常式と比較してみましょう。

f:id:Hassium277:20200304221507p:plain

一発式が通常式を常に上回るようです。

ついでに「一発式の即決確率÷通常式の即決確率」の値も見てみましょう。

f:id:Hassium277:20200304221529p:plain

ものすごい勢いで増加していきました。

ということは、人数が増えれば増えるほど一発式の優位性が高まるという事が分かります。

人数減少率 $=1-\frac{(n-1)(5n×4^{n-1}-10n(n-1)×3^{n-2}+10n(n-1)(n-2)×2^{n-3}-5n(n-1)(n-2)(n-3))}{n×5^n}$

一発式は「一人勝ち」と「あいこ」の2種類の結果しか起こり得ないので、計算がめっちゃ楽でした。

f:id:Hassium277:20200304221658p:plain

f:id:Hassium277:20200308001735p:plain

1に収束し、通常式より高効率です。(人数減少率は数値が小さいほど高効率です)

長所

・特になし

短所

・確率が均一でない

実は各参加者がランダムに手を出す場合、勝つ確率は手ごとに均一ではありません。

具体的な勝率は以下の通りです。

$5 : \frac{n×4^{n-1}}{5^n}$
$4 : \frac{n×4^{n-1}-n(n-2)×3^{n-1}}{5^n}$
$3 : \frac{n×4^{n-1}-2n(n-1)×3^{n-2}+n(n-1)(n-2)*2^{n-3}}{5^n}$
$2 : \frac{n×4^{n-1}-3n(n-1)×3^{n-2}+3n(n-1)(n-2)*2^{n-3}-n(n-1)(n-2)(n-3)}{5^n}$
$1 : \frac{n×4^{n-1}-4n(n-1)×3^{n-2}+6n(n-1)(n-2)*2^{n-3}-4n(n-1)(n-2)(n-3)}{5^n}$

f:id:Hassium277:20200304230708p:plain

なお、冒頭のツイートの投稿者曰く「心理戦になるから面白い」とのことなので、これを短所と呼んでよいのかは微妙なところです。

私の個人的な感想としては、じゃんけんの度にわざわざ心理戦を強いられるのは面倒だと思います。

ゲーマー式

冒頭のツイートへのリプで、「ゲーマーじゃんけん」というものについて言及したものがありました。

ルール

・手の出し方は通常式と同じ

・同じ手を出した人が最も少ない人が勝ち

　例：(G,C,P)=(3,2,4)→Cの2人が勝ち

・最少の手が2つの場合は通常式で判定

　例：(G,C,P)=(3,4,3)→最少はGとPなのでPの3人が勝ち

即決確率 $=\frac{n×2^{n-1}-n(n-1)}{3^{n-1}}$

f:id:Hassium277:20200305004206p:plain

f:id:Hassium277:20200305004544p:plain

赤：通常式
青：一発式
緑：ゲーマー式

即決確率は通常式より高く、一発式より低いようです。

人数減少率 $=???$

すみません、計算できませんでした。

何度式を立て直しても計算が合わず、最終的にググって出た式をそのままパクろうとしたものの、

f:id:Hassium277:20200306153350p:plain

マイナスになりました。

長所/短所

・特になし

良くも悪くも「無難」という印象です。

拡張式

ふと思ったんですが、じゃんけんの手の種類って3種以上に増やせないんでしょうか？

例えば、

f:id:Hassium277:20200306180211p:plain

これは通常式ですが、これを

f:id:Hassium277:20200306180223p:plain

こうしてもいいわけです。

また、ここからさらに増やして、手の種類を任意の奇数(偶数だと対称性が崩れます)に拡張することもできるはずです。

というわけで、そのような場合の性質を検証してみます。

ルール

・ $2m+1$ 通りの手を出せる(1～ $2m+1$ の番号を振る)

・個人判定： $a>b$ の場合、 $a+b$ が偶数なら $a$ の勝ち、奇数なら $b$ の勝ち(同じ手のみあいこ)

・全体判定：個人判定で負けが無かった参加者が勝ち

即決確率 $=n×(\frac{m}{2m+1})^{n-1}$

拡張式の場合、ある特定の手に負ける手は $m$ 種類あるのでこうなります。

f:id:Hassium277:20200306191205p:plain

$m=1→n×(\frac{1}{3})^{n-1}$ 　(通常式)
$m=2→n×(\frac{2}{5})^{n-1}$
$m=3→n×(\frac{3}{7})^{n-1}$
$m=4→n×(\frac{4}{9})^{n-1}$
$m=5→n×(\frac{5}{11})^{n-1}$

一応 $m$ が増えると確率は上がるようですが、変化は小さいです。

ちなみに $m$ を増やし続けるとだんだん $\frac{n}{2^{n-1}}$ に近づいていくんですが、

f:id:Hassium277:20200306192839p:plain

一発式とゲーマー式に負けます。

つまり、手の数を無限に増やしても一発式とゲーマー式には敵わないという事です。

人数減少率 $=1-\frac{(m+1)^n×m^{n+1}-m^{2n+1}-m^{n+1}-(m+1)^{n-1}×m+1}{(2m+1)^{n-1}×m^{n+1}}$

f:id:Hassium277:20200308010610p:plain

赤： $m=1$
青： $m=2$
緑： $m=3$
オレンジ： $m=4$
紫： $m=5$

手の種類が増えると一応人数減少率は下がるようですが、 $m=8$ あたりからはもうほとんど誤差です。

短所

・ルールが複雑で判定が面倒臭い

そりゃそうです。

長所

・特になし

代表式

大勢でのじゃんけんといえば、小学生の時に「教員一人が代表となり、代表に勝った参加者が勝ち」という形式でじゃんけんをした記憶があります。

当時は何も考えずに参加していましたが、今になって考えてみるとかなり効率的な方法であるように思えます。

というわけで、検証してみます。

即決確率 $=\frac{n}{3}×(\frac{2}{3})^{n-1}$

※代表は参加者の人数に含んでいません。

f:id:Hassium277:20200306220528p:plain

赤：通常式
青：一発式
緑：ゲーマー式
紫：代表式

$n=2$ では最下位ですが、その後通常式を追い抜くようです。

ついでに一発式とゲーマー式の確率比も見てみます。

f:id:Hassium277:20200306222311p:plain

一発式÷代表式

やはり一発式の即決確率の高さは凄いですね。

f:id:Hassium277:20200306222449p:plain

ゲーマー式÷代表式

3に収束していくようです。

人数減少率 $=\frac{1}{3}+(\frac{2}{3})^n$

f:id:Hassium277:20200307221151p:plain

なんと、今までのものとは違い1ではなく $\frac{1}{3}$ に収束していきます。

人数減少率が $\frac{1}{3}$ ということは、1回の試行ごとに人数が $\frac{1}{3}$ 倍に減っていくということになります。

効率の良さが分かりやすいですね。

長所

・実行しやすい

ルール的には通常式とほぼ同じため、簡単な説明で実行できることが期待できます。

また、勝利判定時に全員の手を見る必要が無いため、人数が多くても判定が容易であるという点も魅力的です。(ただし結果の偽装も容易なので注意が必要です)

短所

・代表が要る

代表は必ず参加者以外から選ぶ必要があるため、状況次第では実行しづらいです。

例えば、無人島に漂着して、その島に封印されていた邪神に生贄を捧げる場合、邪神に代表を務めてもらうために交渉する必要があります。

巡回式

代表式の短所を克服する方法を思いつきました。

ルール

・円環状に並び、中心を向く

・各参加者は、自分の右隣の参加者の手を見て勝利判定を行う

即決確率 $=???$
人数減少率 $=???$

すみません、計算できませんでした。

とりあえず感覚的な予想として、人数が多くなってきたときの性質は代表式と同じ感じになりそうです。

長所/短所

・特になし

「並ぶために広い場所が要る」という短所があるように思えますが、手の確認のしやすさを考慮すると他の方式(代表式を除く)でも円環状に並んだほうが良いように思えます。

また、「誰が誰を見て判定するか」さえ決まっていれば円環状に並ばなくてよいような気もします。(確率が均等になるかわからないし、もはや「巡回式」ではなくなりますが)

実践

ここまで読んだ人の中には、「数式やらグラフばっかで何言ってるかわかんねぇぞカス」とか「即決確率やら人数減少率やらを見せられたところで結局どれが一番早く終わるのかわかんねぇだろ間抜け」と思っている方も多いでしょう。

また、書いてる側としては「計算できなかった」として諦めた部分を何とかしたいという気持ちがあります。

というわけで、実際にじゃんけんをして確かめてみたいと思います。

しかし、ザ・ボッツェストである私には大人数を集めて実験するなんてことは不可能です。

じゃぁどうするか？

f:id:Hassium277:20200308220131p:plain

自動化します。

(1) 各方式について「人数を指定するとその人数でコンピュータがじゃんけんをして、残り人数を返す関数」を作る

(2) 人数が残り1人になるまで(1)の関数を繰り返し実行し続け、試行回数を出力する

(3) (2)を5000回繰り返し、試行回数の平均値を求める

...という手順で検証を行います。

まずは冒頭の一発式の動画に合わせて、7人でやったときに一人の優勝者が決まるまでの平均試行回数を計算してみます。

通常式	8.6658回
拡張式(m=2)	9.1552回
拡張式(m=3)	9.301回
拡張式(m=4)	9.4268回
代表式	2.864回
巡回式	2.3126回
ゲーマー式	1.6586回
一発式	1.1854回

通常式と拡張式が飛びぬけて多く、他は僅差ですが一番少ない回数で終わるのは一発式でした。

ところで、拡張式の数値を見てみると手の種類が多くなるほど平均回数は増えていっています。

つまり拡張式は存在意義のないゴミということですが、他の方式と組み合わせた場合どうなるのでしょうか。

というわけで、先程と同じく7人で実験してみました。

	3	5	7	9
ゲーマー式	1.6586回	1.3388回	1.6264回	1.19694回
代表式	2.864回	3.0476回	3.0624回	3.1728回
巡回式	2.3126回	2.4596回	2.5238回	2.6196回

ゲーマー式は若干変な動きをしていますが、やはり手の数が増えると平均回数は増えるようです。

...と思いきや、

	3	4	5	6	7	8	9
一発式	2.5804回	1.4296回	1.1854回	1.096回	1.0528回	1.037回	1.025回

※一発式は手の種類を奇数にする必要がありません

一発式だけは手の種類を増やすと回数が減るようです。

なんでやねん。

さて、ここまではあくまでも予選のようなもの。

「大人数で効率よくじゃんけんをする方法を検証した」というからにはもっと大人数で実験するべきでしょう。

というわけで、50人まで増やします。

※何で予選をする必要があるのかというと、通常式と拡張式を50人でやるととんでもなく時間がかかるからです。ググったところ通常式の平均回数は約2億回だそうです。

一発式	1399.465回
代表式	4.6262回
巡回式	4.0908回
ゲーマー式	3.3128回

何という事でしょう、予選で最少記録を叩き出した一発式が、決勝戦では他3方式にものすごい大差をつけられ敗北してしまいました。

というわけで、大人数での最も効率の良いじゃんけんの方法は、

ゲーマーじゃんけんです！！！

「無難」とかいってすみませんでした。

さて、いかがでしたでしょうか。

書いてる側としては、即決確率と人数減少確率の計算が死ぬほど面倒臭くて、その計算が終わった後にコンピュータによる実験をしたところ圧倒的にわかりやすいデータが一瞬で出たので「俺の今までの苦労は何だったんだ」ってなりました。

なお今回は平均試行回数で最終的な決着をつけましたが、「平均試行回数の少なさ」だけが「効率の良さ」を表すというわけではないと思っています。

なのでもし「[理由]だから[方式]の方が効率的なのでは？」という意見があればご自身で検証してみてはいかがでしょうか。

それでは、さようなら。

偽計数学妨害罪

うるせぇ、こっちは遊びで数学やってんだよ

大人数で効率よくじゃんけんをする方法を検証した

検証方針

通常式

一発式

ゲーマー式

拡張式

代表式

巡回式

実践