素数を使ったじゃんけんの問題点とその解決策


素数を使ったじゃんけんについて前回書きましたが、
よく考えるとこのじゃんけんには問題があります。

この後長々と書いていますが、
結論から言うと、解決方法はわかりませんでした。
何か一般的に知られた方法はあるんでしょうか?

問題点

何かと言うと、
2人でじゃんけんするときはいいのですが、
例えばAさん、Bさん、Cさんの3人でじゃんけんする場合に、
AさんとBさんが結託して
「Cさんにできるだけ勝たせないようにしよう」
という操作が可能になってしまうことです。

∞のじゃんけんをする場合に、
Aさんが0、
Bさんが0.499 (0.5を下回るできるだけ大きい数)を選ぶと、
Cさんが1番になるのは、5/6~1の間だけ、つまり、勝つ確率がほぼ1/6になってしまいます。

もっと極端な例だと、
4人でじゃんけんして、
Aさんが0、
Bさんが0.01、
Cさんが0.499を選ぶと、
Dさんが1番になるには、
Cさんと同じ値を選んで「同率1位」になるしかありません。

後出しが禁止なのはある意味当然のことなので、
それができないような仕組みは考えればいいのですが、
このように何人かが結託した場合に他の人が極端に不利になるのはよくありません。

「応募者全員でじゃんけんして、1番の人に賞品を差し上げます!」
みたいなことをしたい場合にも、
例えば10回分の応募券を手に入れた人が、
0, 0.001, 0.002, ・・・, 0.009 と、0.4999
を選ぶと、0.4999が勝ちやすくなります。

なので、
勝敗の定義を改良したいところです。

ここで言う「じゃんけん」の定義は

さて、
ここで言っている「じゃんけん」とは、そもそもどういうものと定義できるでしょうか?

簡単に言うと、
「手の種類と、勝敗のルールを定めたもの」
ですが、より本質的に考え、
「集合Aに対し、Aの各有限部分集合αの順序を定めること」
としましょう。

例えば、
{0,1,2,3,4}
という5つの要素からなる集合に対して、

{組み合わせ}→(順位)
{0,1}→(1,0)
{0,5}→(0,5)
{0,1,2}→(2,1,0)

という形で、全ての組み合わせに対して、「0と1なら、1が1位、0が2位」
などと、順位を定義すればよいということになります。
(右側のかっこで囲ったものは、左から順に1位、2位、・・・という順番だという意図で書いています。)

定義さえすればなんでもよいのですが、可能であれば、
「全ての要素が対等」
としたいところです。

3人のじゃんけんの定義

いきなり手の種類の数を増やすと大変なので、できるだけ少ないところから考えてみましょう。

ここで考えたいのは、AとBとCの3人でじゃんけんする場合に、
「AとBがどの2つの手を出していても、Cが勝つ確率が1/3である」
を満たすものですが、より強く、
1位、2位、3位が、
A→B→C
A→C→B
B→A→C
B→C→A
C→A→B
C→B→A
の6通りのどれになるかの確率がそれぞれ1/6になるものを考えましょう。

これを実現するための、最小の手の種類の数は、8です。
2人や4人のじゃんけんの勝敗は置いておいて、
{0,1,2,3,4,5,6,7}
から3つを選ぶ組み合わせに対して順序を定義した、
3人のじゃんけんを考えてみます。

「勝ち点の合計」のような単純なルールから離れて一般的に考えるとなると、
大変複雑なのですが、
ちょっとプログラムを書いて検証したところ、
上記の条件を満たす組み合わせがあることがわかりました。

その一例が以下です。

(0, 1, 2)
(0, 3, 1)
(1, 0, 4)
(5, 0, 1)
(1, 6, 0)
(7, 1, 0)
(0, 2, 3)
(4, 0, 2)
(2, 0, 5)
(6, 2, 0)
(2, 7, 0)
(3, 4, 0)
(5, 3, 0)
(3, 0, 6)
(7, 0, 3)
(4, 5, 0)
(0, 6, 4)
(0, 4, 7)
(0, 5, 6)
(0, 7, 5)
(6, 0, 7)
(3, 2, 1)
(2, 4, 1)
(1, 5, 2)
(2, 1, 6)
(1, 2, 7)
(3, 1, 4)
(1, 3, 5)
(6, 1, 3)
(1, 7, 3)
(4, 1, 5)
(1, 4, 6)
(4, 7, 1)
(6, 5, 1)
(5, 1, 7)
(7, 6, 1)
(2, 3, 4)
(2, 5, 3)
(6, 3, 2)
(3, 7, 2)
(5, 2, 4)
(4, 2, 6)
(7, 4, 2)
(5, 6, 2)
(7, 2, 5)
(2, 6, 7)
(5, 4, 3)
(4, 6, 3)
(4, 3, 7)
(3, 6, 5)
(3, 5, 7)
(7, 3, 6)
(6, 4, 5)
(7, 5, 4)
(6, 7, 4)
(5, 7, 6)

8つから3つを選ぶ組み合わせの総数が56もあるのでもうわけがわかりませんね。
一応、これの見方は、3つの組み合わせに対して、左から順に(1位, 2位, 3位)の意味です。

これが本当に条件を満たしているのかですが、
例えばAとBが0と4が選んだ場合については、
上記の中から0と4を含むものを抜き出すとわかります。

(1, 0, 4) ・・・ A:2位, B:3位, C:1位
(4, 0, 2) ・・・ A:2位, B:1位, C:3位
(3, 4, 0) ・・・ A:3位, B:2位, C:1位
(4, 5, 0) ・・・ A:3位, B:1位, C:2位
(0, 6, 4) ・・・ A:1位, B:3位, C:2位
(0, 4, 7) ・・・ A:1位, B:2位, C:3位

と、確かに、Cがどれを選ぶかで次第で3人の順位がどのようにも変わることがわかります。

ですが、
こんな例を一つ上げただけでは、4人以上のじゃんけんや、
手の種類の数を増やした場合の一般化がわかりません。

もう少し、構造がわかるようにする手はないでしょうか?

そこで、この「勝敗表」の表示方法を変えることを考えました。

8個から3つ選ぶ組み合わせを漫然と上から並べているだけだとわかりにくいので、
次のルールで並べます。

まず、最初は何でもいいのですが、例えば(0, 1, 2)から始めて、
この次には、(1, 2, *)で始まるものを持ってきます。
探してみると、(1, 2, 7)が該当します。
上記の勝敗表の性質から、このように最初の2つを指定すると、
それで始まるものがただ一つ存在することがわかります。

なので、それらを取ってきて順番に並べてやります。

(0,1,2)-(1,2,7)-(2,7,0)-(7,0,3)-・・・

これはいつかループして左に戻ります。
重なっている部分を除いて以下のように書くとわかりやすくなります。

01270314632160754372530645

一番右に行ったあとは左に戻ります。
このループですが、見ての通り26文字しかありません。

残ったものもループを形成するので全部上げると以下のようになります。

01270314632160754372530645
13576
17365
0234
0471
0562
1524
2674

この、ループを形成する個数が、

26,5,5,4,4,4,4,4

となっているところが興味深いですね。
8とも3とも関係のなさそうな数字が並んでいます。

他の勝敗ルールも検証してみたところ、
ループを形成する個数が以下のパターンが見つかりました。

49,7
37,10,9
26,5,5,4,4,4,4,4
23,8,5,4,4,4,4,4
22,11,11,4,4,4
21,13,10,4,4,4
17,11,7,5,4,4,4,4
12,12,6,6,6,6,4,4
10,10,10,10,4,4,4,4
8,8,4,4,4,4,4,4,4,4,4,4
7,7,7,7,7,7,7,7

少なくともこれらの勝敗ルールは、
互いに本質的に異なるものであることがわかります。

色々あることはわかりましたが、
この中で気になるのは一番下ですね。
7つで形成されるループが8つ。
これが単純なパターンであれば、
うまく拡張することで、
手の種類の数を増やした場合や、人数を増やした場合を考えることができるかもしれません。

この最後のパターンについて、先ほどのようにループを形成する手の種類を並べてやると以下のようになりました。

1234567
0472653
4051376
7506241
2160735
6327014
5743102
3615420

上手く拡張できるような気が、
するようなしないような。
私が考えたのはここまでです。

どなたか、何かわかったら教えてください。

Category: 数学 | Tags: ,