【初月無料キャンペーン中】gooドクター

12名で年6回ゴルフコンペを行っております。
4名1組で計3組でラウンドしておりますが
この6回の内に他の11名すべての人と
なるべく重複しないように組を組むには
どういった組み合わせ方をすれば
良いでしょうか?
宜しくお願い致します。

A 回答 (5件)

 「みんなに一度は当たる」というだけの条件だったら、高々5回のラウンドでできちゃうんです。



 まず、条件を追加して、手作業で扱える程度の問題に帰着してしまいます。どんな条件かと言うと:
 12人のメンバーを1さんから12さん、と呼ぶことにします。(いや、●chとは関係ないです。)
で、二人ずつペアになって貰います。
ペア1は1さんと7さん、ペア2は2さんと8さん、ペアnはnさんとn+6さん(n=1~6)
こうして決めたペアはいつも一緒の組になる。これが追加した条件です。
 そうすると、
ラウンド1ではペア1~6はそれぞれA組,A組,B組,B組,C組,C組
ラウンド2ではペア1~6はそれぞれA組,B組,A組,C組,B組,C組
ラウンド3ではペア1~6はそれぞれA組,B組,C組,A組,C組,B組
ラウンド4ではペア1~6はそれぞれA組,B組,C組,B組,A組,C組
ラウンド5ではペア1~6はそれぞれA組,B組,B組,C組,C組,A組
という解がすぐ見つかりました。
 どのペアも他の5つのペアと一度は一緒にラウンドしてます。ですから、どの人も他の人全員と一度はラウンドしたことになる。だからこれで、「みんなに一度は当たる」という条件を満たしています。

 ただ、この組み合わせ方では、どの人もペアを組んだ相手とはいつも一緒である。これをもっと散らして平準化したいですね。

 そこで1~6さんは上記の組み合わせに従って戴くとして、7~12さんには以下のように組を代わって貰います。
ラウンド2と3ではA組と言われたらB組へ、B組と言われたらC組へ、C組と言われたらA組へ行く。
ラウンド4と5ではA組と言われたらC組へ、B組と言われたらA組へ、C組と言われたらB組へ行く。
 こうしますと、5回のラウンドのうちで、どの人も他の全員と当たり、しかも高々3回しか同じ人と当たりません。
 3回当たるのは
(1,8),(2,7),(3,10),(4,9),(5,12),(6,11)
 2回当たるのは
(1,9),(1,10),(2,9),(2,10),
(3,11),(3,12),(4,11),(4,12),
(5,7),(5,8),(6,7),(6,8)
で、他の「二人の組み合わせ」は1回ずつ当たります。

 ところで、6回のラウンドを有効に使えばもっと平準化できる(同じ人と1回しか当たらないということを減らすとともに、同じ人に3回当たるという組み合わせを少なくできる)に違いなく、コンピュータで力任せに探索すればナントカなるはず。そのうちやってみるかも知れません。
    • good
    • 1
この回答へのお礼

詳しい例をあげて頂きありがとうございます。
2回続けて同じ人とラウンドすることは
実際多々ありましたので組合せ的に避けられないことだと
思っていました。
今回このパターンに当てはめて組合せ表を
作ってみたところ3回当たる(2.7)の人だけ
連続3回一緒にラウンドすることになりますが
これはラウンド2を最後に回すことで
回避出来ますよね?
お忙しいところありがとうございます。

お礼日時:2003/12/07 21:23

odenon909さん、今晩は。

#1のものです。この週末に
家でプログラムを作って結果を出そうとしたら土日とも
休日出勤と相成ってしまいました。(泣)
さて、私もstomachmanさんの条件(1')(2)(3)を充たすものを探そうとしています。

(1') 任意の対は高々3回しか実現しない。
(3) 任意の対が少なくとも一回は実現される。
(2) 3人の組合せは高々一回しか実現しない。

で、プログラミングの方針として次の二つのものを立てました。
この方針に則ってプログラムを作ってくれる奇特な人はいないかな。
ただ、組み合わせ論に慣れた人でないと結構大変だろうけど。
勿論時間ができれば、私が作ります。(締め切られていない場合ですが)

方針1 強引な方法
ラウンドとは12人を4人からなる3つの集合に分割したもの。
(以降は、便宜上10番目、11番目、12番目の人を夫々A,B,Cで表わす)
従って、その全体(以下ROUNDとする)はC(11,3)C(7,3)=5775通り。
第1ラウンドは次のように決めて良い。
R1:[1234][5678][9ABC]
従って、2~6ラウンドをどう決めるかが問題。

1 12人中の3人の組合せは全部でC(12,3)=220通りだが、R1で12通りの
3人組みが既に実現されている。この12通りの集合をAとする。

2 12人中の4人の組合せは全部でC(12,4)=495通りだが、R1の4つと
集合Aを含む4人組みを全て取り除く。得られた集合をXとする。

3 ROUNDからXの要素に含まれない4人組みを含むラウンドを取り除く。
得られた集合をYとする。

ここでかなりのギャップ。

4 Yの要素の5個の組で同じ3人組を含まないものを全て求める。

5 4で得たものの中で、条件(2)(3)を充たすものを取出す。

方針2(組合せ理論のある定理を使った方法)はまた明日にでも
書き込みます。但し、その定理が有効かどうかはまだ見えていません。
単なる使ってみたいだけと言う事もあります。
    • good
    • 0

 そうスッキリとは行きそうにない問題で、すぐには検討できないんで、とりあえずチョコチョコとプログラムを書いて走らせてみました。

No.1の回答と似たような発想で、
(1) 誰も、同じ人とは高々2回しか同じ組にならない。
という条件を付け、さらに、
(2) ある組において、3人以上が以前のコンペで同じ組だった、ということはない。
を条件としてみました。
 で、結果ですけれど、この二つの条件を付けたとき、5回はコンペができますが、6回やる方法はどうもないみたいです。(勿論、プログラムのチョンボの可能性もありますが。)

 ですから、条件を緩めなくてはいけません。どう緩めましょうか。まずは
(1') 誰も、同じ人とは高々3回しか同じ組にならない。
としましょう。それから、実際問題としてはおそらく
(3)どの二人をとっても、6回のコンペのうち少なくとも一度は一緒の組になる。
が重要ではないでしょうか。せっかくのコンペですもんね。だから今度は、(1')(2)(3)の三つを条件にしてみようかと思います。ただ、この条件では計算時間も格段に増えると予想され、コンピュータで探索するのもいつになるやら…
    • good
    • 1
この回答へのお礼

皆様お忙しいところ回答下さいましてありがとうございます。 感謝しております。
自分が幹事をしているので旨く年を通して
皆とあたるようにずっと考えていたんですが
どうしても2人は続けて重なってしまうのですね。
これが4組だと簡単かな?
同じ人と続けてあたるのは良しとして
うまく組を作る方法などありますでしょうか?
たとえば乱数表のようなもので、、、。
お暇な時で結構ですのでお知恵を拝借させてください
宜しくお願い致します。

お礼日時:2003/12/03 21:56

なるべく重複しないようにというのは、


例えば、

Aさんの組には毎回のように
一緒にラウンドした人がいるが
他の人はあまり重複していない

というのと、

みんな平等に重複している

のとでは、どちらがなるべく重複してないのですか?
    • good
    • 0

odenon909さん、今晩は。


御質問は方針を求めているのでしょうか、それとも
具体的な回答を求めているのでしょうか。後者のような気がしますが、それは簡単には行かないので、まずは方針だけ。

12人ですから対は全部でC(12,2)=66個あります。また、一ラウンドで4人一組ですから、一組が
含む対はC(4,2)=6個、それが3組ですから
一ラウンドは18個の対、年6回で108個の対となります。
少なくとも108-66=42個の対が重複しますから、1回だけ実現される対が24個、2回実現される対が42個となるようなものが選べれば多分それがご希望の組合せでしょうね。

p.s. 私は趣味で似たような幾何学的問題を考えています。そちらの理論が応用できそうな気がするのでさらに
考えてみます。
    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!


人気Q&Aランキング