改良版じゃんけん「ツーペン」の効率について

こんにちは。最近「ゆる言語学ラジオ」という youtube チャンネルをよく視聴するのですが、そのチャンネルのとある動画でじゃんけんの改良版「ツーペン」が紹介されていました↓

動画ではルールの紹介のあと、通常のじゃんけんとの効率性の比較の際に数学が役に立ったというエピソードが続きます。そこでこの記事ではこの検証を改めてやってみたいと思います。

ルール
ポイントの整理
勝敗決定までにかかる時間の検証
効率性以外のツーペンの問題点

ルール

ツーペンでは、以下のルールに則って2人以上の参加者から1人の勝者を決めることができます。

以下を基本手順と呼ぶこととする:

開始時の参加人数を $n$ とする。
【 $n = 2$ の場合】

2人をそれぞれ親または子とする

「ツーペン！」の掛け声とともにそれぞれグーまたはチョキを出す

手が同じなら親の勝ち、手が異なるなら子の勝ち

【 $n \geq 3$ の場合】

「ツーペン！」の掛け声とともにそれぞれグーまたはチョキを出す

それぞれの手を出した人数を数える

小数の手を出した人が勝ち。ただし全員同じ手の場合やちょうど半々の場合は全員あいことする。

基本手順を実行して勝者(またはあいこ)のみを残すことを繰り返すことで参加者を減らしていき、最終的に残った1人を全体の勝者とする。

比較のため、通常のじゃんけんのルールも同様の形式で書いておきます。

以下を基本手順と呼ぶこととする:

「じゃんけんぽん！」の掛け声とともにグーまたはチョキまたはパーを出す

全員の手が2種類のみに分かれた場合に、強い手を出した人が勝ち。1種類または3種類の場合は全員あいことする。

基本手順を実行して勝者(またはあいこ)のみを残すことを繰り返すことで参加者を減らしていき、最終的に残った1人を全体の勝者とする。

ポイントの整理

効率性の観点でのじゃんけんと比較したときのツーペンの利点は

あいこがない
少数派が残るためかならず 1/2 以下になる

ことです。通常のじゃんけんは大人数になると勝敗がなかなか決まらない上、決まってもあまり人数が減らない可能性があるため、それらを改良した形となります。
一方でツーペンと比べた場合のじゃんけんの利点は

あいこ判定に必ずしも全員の手を調べる必要がない

ことです。あいこがすぐ判定できるというのはそれなりに時間の節約に役立つものの、ツーペンではそもそもあいこになる確率が低いため、おそらく総じてツーペンのほうが有利になるでしょう。
上記の点を踏まえて、1人の手を確認するのにかかる時間を「1ステップ」という単位で数えて、最後の1人が絞り込まれるまでに平均で何ステップ必要かで比較したいと思います。

勝敗決定までにかかる時間の検証

状態遷移の考え方を導入します。参加人数 $n$ の状態から、一回の基本手順で参加人数 $m$ の状態に移ることを $n \to m$ という風に書くこととします。あいこの場合は $n \to n$ の場合に相当します。この記法により、あいこの場合と勝敗が決まった場合を同じように取り扱うことができます。さらに参加者数が $n$ のときに基本手順の結果状態遷移 $n \to m$ を起こす確率を $p_{n \to m}$ 、またその際の平均的に必要なステップ数を $s_{n \to m}$ と表すこととします。さらに複数回の基本手順を含めて最終的に1人の勝者を決めるまでに必要な平均的なステップ数を $t_{n}$ とします。このとき

$\begin{gather} t_{n} = \sum_{m = 1}^{n} p_{n \to m}(s_{n \to m} + t_{m}) \\ \end{gather}$

が成立します。両辺に $t_{n}$ が入っているので、整理して $t_{n}$ について解いてみると

$\begin{gather} t_{n} = \frac{1}{1 - p_{n \to n}} \left\{ p_{n \to n} s_{n \to n} + \sum_{m = 1}^{n - 1} p_{n \to m}(s_{n \to m} + t_{m}) \right\} \end{gather}$

が得られます。よって、 $p_{n \to 1}, p_{n \to 2}, ..., p_{n \to n}$ と $t_{1}, t_{2}, ..., t_{n-1}$ と $s_{n \to 1}, s_{n \to 2}, ..., s_{n \to n}$ が分かっていれば $t_{n}$ を求めることができます。 $t_{1}, t_{2}, ..., t_{n-1}$ については帰納的に定めることができるので、残りの $p_{n \to 1}, ..., p_{n \to n}$ および $s_{n \to 1}, ..., s_{n \to n}$ をどうやって求めるか考えてみましょう。

普通のじゃんけんの場合

まず $p_{n \to m}$ について考えます。 $n > m$ の場合は $m$ 人が勝つパターンなので、勝つ人を選ぶ ${}_{n}\mathrm{C}_{m}$ 通り、勝ち負けの2種類の手の選び方 $3$ 通りで、都合 $3 {}_{n}\mathrm{C}_{m}$ 通りあります。よって $p_{n \to m} = \frac{3{}_{n}\mathrm{C}_{m}}{3^{n}} = \frac{{}_{n}\mathrm{C}_{m}}{3^{n-1}}$ となります。 $n=m$ の場合、すなわちあいこのときは、手の種類が2種類でない場合に相当するので、全部で $3^{n} - 3 \times (2^{n} - 2)$ 通りあります。よって $p_{n \to n} = \frac{3^{n} - 3 \times (2^{n} - 2)}{3^{n}}$ となります。以下にまとめておきます:

$\begin{gather} p_{n \to m} = \begin{cases} \dfrac{{}_{n}\mathrm{C}_{m}}{3^{n - 1}} & (1 \leq m < n) \\ 1 - \dfrac{2^{n} - 2}{3^{n - 1}} & (m = n) \end{cases} \end{gather}$

次に $s_{n \to m}$ について考えます。 $n > m$ の場合は、 $n$ 人のうちひとりだけ手を変えるとあいこになりうることを考えれば、 $s_{n \to m} = n$ であることが分かります。一方で $n = m$ についてはある3人が別々の手を出していることを発見すればその時点であいこになってしまいます。よって、一人ひとりの手を順番に見ていったときに、 $k$ 人目の手を確認したときにはじめて3種類の手が揃う確率、などを考慮する必要があります。すべて説明すると時間がかかりまくるので途中省略すると、

$\begin{gather} s_{n \to n} = \dfrac{(4n + 3) - (n + 3) 2^{n + 1} + 11 \times 3^{n - 1} }{2 \{ 3^{n - 1} - (2^{n} - 2)\}} \end{gather}$

となります。人数が多いときはおおよそ5.5人ぐらい確認するとあいこが判明するようです。6人以上でじゃんけんするときは結構辛くなりそうな予感がします。

ツーペンの場合

まず $p_{n \to m}$ について考えます。 $n = 2$ のときは勝敗が必ず決まるので $p_{2 \to 2} = 0, p_{2 \to 1} = 1$ です。以下 $n \geq 3$ とします。 $n > m$ の場合、 $\frac{n}{2} \leq m$ のときは $p_{n \to m} = 0$ です。なぜなら勝つのは決まって少数派だからです。 $\frac{n}{2} > m$ の場合は、勝つ人の選び方が ${}_{n}\mathrm{C}_{m}$ 通り、少数派が選ぶ手の種類が $2$ 通りなので、合わせて $2 {}_{n}\mathrm{C}_{m}$ 通りあります。よって $p_{n \to m} = \frac{2 {}_{n}C_{m}}{2^{n}} = \frac{{}_{n}C_{m}}{2^{n-1}}$ となります。 $n = m$ の場合、すなわちあいこの場合は $n$ が奇数の場合は $p_{n \to n} = \frac{2}{2^{n}} = \frac{1}{2^{n - 1}}$ , $n$ が偶数の場合は $k = \frac{n}{2}$ として $p_{n \to n} = \frac{2 + {}_{n}\mathrm{C}_{k}}{2^{n}}$ となります。以下にまとめておきます:

$\begin{gather} p_{2 \to 1} = 1, \\ p_{2 \to 2} = 0, \\ p_{n \to m} = \begin{cases} \dfrac{{}_{n}\mathrm{C}_{m}}{2^{n - 1}} & \left(1 \leq m < \dfrac{n}{2}\right) \\ 0 & \left(\dfrac{n}{2} \leq m < n \right) \\ \dfrac{1}{2^{n - 1}} & (m = n, n が奇数) \\ \dfrac{2 + {}_{n}\mathrm{C}_{n/2}}{2^{n}} & (m = n, n が偶数) \end{cases} \qquad (n \geq 3) \end{gather}$

次に $s_{n \to m}$ について考えます。実は $m$ によらず $s_{n \to m} = n$ が成立します。これは全員の手が判明するまで基本手順の結果が(あいこの場合も含めて)決まらないことから分かります。すなわち仮に $n - 1$ 人の手が決まったとしても、最後のひとりが残るのか脱落するのか判定できません(どちらの手を出すかによって結果が変わる)*1。よって必ず $n$ ステップ必要で、 $n$ ステップあれば OK となります。

数値計算の結果

$t_{n}$ を手計算するのは現実的ではないので、python で書き飛ばしコードを作ってプロットしてみました。
f:id:mat_der_D:20211103141412p:plain
その差は歴然です。通常のじゃんけんの方は人数に対して指数関数的に伸びているのに対し、ツーペンでは概ね線形で抑えられています。例えば $n = 8$ の場合は5倍近くの差があるようです。