View difference between Paste ID: <a href="/Pn50Nphn">Pn50Nphn</a> and <a href="/2xJCbXEZ">2xJCbXEZ</a>

/*
1		/*
2		入力: n人の生徒
3		出力: n人の生徒に対するランダムな番号[1..n]
4		条件: 複雑な計算を要しないこと。必ず停止すること。n人のうちランダムにm人選びたいときも応用がきくこと。ランダムであること。戦略的に自分が不利になることはあっても、有利にはなりにくいこと。同時に数字を言う、などではなく、じゃんけんのように、同時に手を出すなどして極力曖昧さが少なくなるようにすること。アルゴリズムが人数によらないこと。ディーラーを必要としないこと。
5
6		じゃんけん[停止しないので不可]
7		n人で誰かが勝つまでじゃんけんをする
8		-> m人が勝ったら、n-m人とm人でそれぞれじゃんけんをする。これを繰り返して一番勝った人から番号を振る
9
10		ゲーマーじゃんけん[停止しないので不可]
11		n人で手を出す
12		-> 手が少ない人たちが勝つ。手が少ない人のグループが同数の時は正規のじゃんけんの方法でグループを一つに決める。これを繰り返して一番勝った人から番号をふる。
13
14		par ou impar[停止しないので不可]
15		-> 全員0または1を出す。少ない方が勝つ。これを繰り返す。2人になったら出す手の和の偶奇を当てる。
16
17		オリジナルの方法
18		2, 3人のグループに別れる。それらの人々の間では勝負が簡単かつ確実につく。
19
20		グループが3人の場合
21		0, 1, 2
22		の中で数字を各人予想する。同時に
23		どれを選んでも当確率である。
24		それぞれ同時に0,1,2またはmod3のことなる3数のうちいずれかを出す　👊,👆,👋(5≡2mod3)
25		予想の当たったものが勝者になる。
26
27		和の場合の数を次のようにして考えられる。プレイヤーAの手とBの手を固定すると、Cが出すべき手cは
28		a+b≡x のとき一意に決まる。つまり、自分が予想した手になるような出し方は3つの手のうち一つしか無い。ところで、xとしては(0+0)(0+1)(0+2)(1+0)(1+1)(1+2)(2+0)(2+1)(2+2)となるが、この内modが何になるかは1/3で当確率。というかaの値を固定して同様に考えれば結局1/3である。
29
30		グループ人数が2人の場合
31		0,1で同じことを行う。
32
33		グループ内での優劣をつける。この優劣は一度でかならず付く。3人の時は勝者の予想した数字-1mod3の数字を予想した人を次点とすればよい。
34
35		こうして選出されたグループの代表者同士で同じことを行う。グループの代表者の数が4人以上でも再帰的にただ一人の勝者を決められる。あるグループAの代表aが勝てば、Bの人間は全てのAの人間に負けたとみなす。
36		例えば
37		a,b,c,d,e,f,g,h,i,j,k
38		についてやってみる。
39		グループ化
40		[a,b,c] [d,e,f] [g,h,i] [j,k]
41		勝った順に並べる
42		[a,c,b] [d,f,e] [g,i,h] [k,j]
43		再グループ化
44		[a,d] [g,k]
45		勝った順に並べる
46		[a,d] [k,g]
47		グループ化
48		[a,k]
49		勝った順に並べる
50		[k,a]
51
52		順序の復元
53		[k,a]
54		[[k,g] [a,d]]
55		[[[k,j],[g,i,h]] [[a,c,b],[d,f,e]]]
56		ただし確認が難しいかも
57
58		一応2n+3m=x(>=2)となるn,m(>=0)の存在を示す
59		x≡0(mod6) -> 3m
60		2人のグループ数: 0
61		x≡1(mod6) -> x≡7 && x >= 7なので 2*2 + 3m に分ける
62		2人のグループ数: 2
63		x≡2(mod6) -> 2*1
64		2人のグループ数: 1
65		x≡3(mod6) -> 3m
66		2人のグループ数: 0
67		x≡4(mod6) -> 2*2
68		2人のグループ数: 2
69		x≡5(mod6) -> x≡11 && x >= 11なので 2 + 3*3 + 3m に分ける
70		2人のグループ数: 1
71
72		計算時間はlog(n)
73		100人でやっても
74		100 -> 34 -> 12 -> 4 -> 2 -> 1
75		となり6回で決まる!
76
77		問題点: グループの作り方がそもそもランダムでないと不都合が生じる。
78		例えば上位勝者半数と敗者半数でチーム分けをするとき、同じチームになりたい人は初戦で戦うことにより同じチームに所属できる確率を高めることができる。
79		このため、より直感的には負けた人のランクで別れるという手がある。全体では勝負回数が増えるが時間は変わらない。このやり方だと
80		例えば
81		a,b,c,d,e,f,g,h,i,j,k
82		についてやってみる。
83		グループ化
84		[a,b,c] [d,e,f] [g,h,i] [j,k]
85		勝った順に並べる
86		[a,c,b] [d,f,e] [g,i,h] [k,j]
87		クラス化
88		[a,d,g,k][c,f,i,j][b,e,h]
89		グループ化
90		[[a,d] [g,k]] [[c,f] [i,j]] [[b,e,h]]
91		勝った順に並べる
92		[[d,a] [g,k]] [[f,c] [i,j]] [[e,b,h]]
93		クラス化
94		[[d,g] [a,k]] [[f,i] [c,j]] [[e,b,h]]
95		グループ化
96		[[d,g] [a,k]] [[f,i] [c,j]] [[e,b,h]]
97		勝った順に並べる
98		[[g,d] [a,k]] [[i,f] [j,c]] [[e,b,h]]
99		並び方はそのまま勝負の順序になっている。しかもたくさん負けた人が後ろに来る
100		だがこの方法だと最初に2人グループに入れられた人はクラス化の時入れられる場所が偏るのでよろしくない・・・
101		*/