最近、ブログばっか書いてるけど。。
オフ会の1対1での会話形式について、
ペア作るときの問題点についてこの前ブログに書いたけど
http://ameblo.jp/standpower/entry-11841581200.html
いまいち理解されてないようなので
もうちょっと詳しく書きます。。。
まず目的として、
例えば、オフ会で10人集まったとして
それぞれが順番に1対1のペアを作って
最終的に全員とペアになれるようにする問題です。
最小のペアの回数は
9回ですね。
1人が9回ペアを作れば、残りの9人全員とペアになって会話できるわけです。
では、よろしくないケースについて説明しましょう。
10人は
Aさん、Bさん、Cさん、Dさん、Eさん、Fさん、Gさん、Hさん、Iさん、Jさん
とします。
まず、
A、B、C、D、Eの5人を固定して、残りのF、G、H、I、Jの5人が順番に相手を変えるようにしますと、
以下のようになります。
■1回目のペア
AとF
BとG
CとH
DとI
EとJ
次にF～Jを1個ずらして
■2回目のペア
AとG
BとH
CとI
DとJ
EとF
同様にF～Jを1個ずらして
■3回目のペア
AとH
BとI
CとJ
DとF
EとG
同様にF～Jを1個ずらして
■4回目のペア
AとI
BとJ
CとF
DとG
EとH
同様にF～Jを1個ずらして
■5回目のペア
AとJ
BとF
CとG
DとH
EとI
ここで、A～Eの人はF～Jの人全員と会話済みとなります。
逆に、F～Jの人はA～Eの人全員と会話済みとなります。
ということは、
A、B、C、D、Eはこの5人内で残りのペアを作らないといけません。
同様に、F、G、H、I、Jもこの5人内で残りのペアを作らないといけません。
もうお分かりかと思いますが、どっちも奇数なので
A～EとF～Jでそれぞれ一人ずつ、計2人が常に余ってしまいます。
■6回目のペア
AとC
BとD
Eがあまり
FとH
GとI
Jがあまり
■7回目のペア
AとD
BとE
Cがあまり
FとI
GとJ
Hがあまり
■8回目のペア
AとE
BとC
Dがあまり
FとJ
GとH
Iがあまり
■9回目のペア
AとB
CとD
Eがあまり
FとG
HとI
Jがあまり
■10回目のペア
CとE
Dがあまり
AとBは完了
HとJ
Iがあまり
FとGは完了
■11回目のペア
DとE
AとBとCは完了
IとJ
FとGとHは完了
これで全員がペアを作り終えました。
最適解は9回なのに、11回になってしまいましたね～
組み合わせを誤るとさらに回数が増えてしまいます（TдT）
人数が偶数にもかかわらず、余りの人もでてしまうという。。
というわけで、
ペア形式のオフをするときは、事前に順番を考えておきましょう♪
というお話でした。