Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- 入力: n人の生徒
- 出力: n人の生徒に対するランダムな番号[1..n]
- 条件: 複雑な計算を要しないこと。必ず停止すること。n人のうちランダムにm人選びたいときも応用がきくこと。ランダムであること。戦略的に自分が不利になることはあっても、有利にはなりにくいこと。同時に数字を言う、などではなく、じゃんけんのように、同時に手を出すなどして極力曖昧さが少なくなるようにすること。アルゴリズムが人数によらないこと。ディーラーを必要としないこと。
- じゃんけん[停止しないので不可]
- n人で誰かが勝つまでじゃんけんをする
- -> m人が勝ったら、n-m人とm人でそれぞれじゃんけんをする。これを繰り返して一番勝った人から番号を振る
- ゲーマーじゃんけん[停止しないので不可]
- n人で手を出す
- -> 手が少ない人たちが勝つ。手が少ない人のグループが同数の時は正規のじゃんけんの方法でグループを一つに決める。これを繰り返して一番勝った人から番号をふる。
- par ou impar[停止しないので不可]
- -> 全員0または1を出す。少ない方が勝つ。これを繰り返す。2人になったら出す手の和の偶奇を当てる。
- オリジナルの方法
- 2, 3人のグループに別れる。それらの人々の間では勝負が簡単かつ確実につく。
- グループが3人の場合
- 0, 1, 2
- の中で数字を各人予想する。同時に
- どれを選んでも当確率である。
- それぞれ同時に0,1,2またはmod3のことなる3数のうちいずれかを出す 👊,👆,👋(5≡2mod3)
- 予想の当たったものが勝者になる。
- 和の場合の数を次のようにして考えられる。プレイヤーAの手とBの手を固定すると、Cが出すべき手cは
- 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である。
- グループ人数が2人の場合
- 0,1で同じことを行う。
- グループ内での優劣をつける。この優劣は一度でかならず付く。3人の時は勝者の予想した数字-1mod3の数字を予想した人を次点とすればよい。
- こうして選出されたグループの代表者同士で同じことを行う。グループの代表者の数が4人以上でも再帰的にただ一人の勝者を決められる。あるグループAの代表aが勝てば、Bの人間は全てのAの人間に負けたとみなす。
- 例えば
- a,b,c,d,e,f,g,h,i,j,k
- についてやってみる。
- グループ化
- [a,b,c] [d,e,f] [g,h,i] [j,k]
- 勝った順に並べる
- [a,c,b] [d,f,e] [g,i,h] [k,j]
- 再グループ化
- [a,d] [g,k]
- 勝った順に並べる
- [a,d] [k,g]
- グループ化
- [a,k]
- 勝った順に並べる
- [k,a]
- 順序の復元
- [k,a]
- [[k,g] [a,d]]
- [[[k,j],[g,i,h]] [[a,c,b],[d,f,e]]]
- ただし確認が難しいかも
- 一応2n+3m=x(>=2)となるn,m(>=0)の存在を示す
- x≡0(mod6) -> 3m
- 2人のグループ数: 0
- x≡1(mod6) -> x≡7 && x >= 7なので 2*2 + 3m に分ける
- 2人のグループ数: 2
- x≡2(mod6) -> 2*1
- 2人のグループ数: 1
- x≡3(mod6) -> 3m
- 2人のグループ数: 0
- x≡4(mod6) -> 2*2
- 2人のグループ数: 2
- x≡5(mod6) -> x≡11 && x >= 11なので 2 + 3*3 + 3m に分ける
- 2人のグループ数: 1
- 計算時間はlog(n)
- 100人でやっても
- 100 -> 34 -> 12 -> 4 -> 2 -> 1
- となり6回で決まる!
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement