場合の数の問題です

「ABCDEFGの８つチームがトーナメント方式で対決する。１回戦４試合、２回戦２試合、決勝戦という組み合わせを一度に決めるとする。トーナメントの組み合わせは何通りあるか。ただし、先攻、後攻の区別や、１回戦４試合、２回戦２試合の試合の順序は考えないものとする。」という問題なのですが、ややこしくて解答見ても理解できません。

解説では、「一回戦について、Aの相手は７通り。その相手が例えばBのとき、残った６チームCDEFGについて考えて、Cの相手は５通り。その相手が例えばDのとき、Eの相手は３通りあり、Eの相手を決めれば残りは自動的にきますから、
一回戦の組み合わせは、7・5・3=105通り
一回戦の勝者をPQRSとすると、２回戦の組み合わせは、Pの相手を決めれば他は一意的に決まり、２回戦の組み合わせは3通り
よって105・3=315通り・・・（答）」となっています。

いっていることはだいたいわかるのですが、はたしてこんな求め方で良いのかという疑問がつきまといます。初めの方で「Aの相手は７通り」となっていますが、肝心のAの位置にくる文字を選ぶ８通りがはずれてしまっているように思えるのですが。よろしくお願いします。

No.4 ベストアンサー 回答者： kony0 回答日時： 2001/10/26 01:19

s-wordさんの考え的には、「８個ある場所に８チームを割り振る」という考えを持っていると思います。

つまり、８個ある場所になんらかの名前を付けて、各々の場所に各チームを入れていく、という考え方であると思います。

さて、８個ある場所はどれをとっても対称だということはおわかりいただけるでしょうか？
たとえばトーナメント図を書いたときの左から順に１～８と名前付けをした場合、「１」と「２（＝１の１回戦での相手）」は対称（「１」と「２」を入れ替えても対戦カードとしては同じ）であり、「１」と「３」も互いに対称（「１」と「３」、「２」と「４」を同時に入れ替えると結局対戦カードとして同じ）である、ということです。
これは「先攻、後攻の区別や、１回戦４試合、２回戦２試合の試合の順序は考えないものとする。」ことから言えることです。

ここで、場所に対する１～８の名前付けはこちらで問題を解く過程で勝手に導入したものですから、上のようにすべての場所が互いに対称である場合、いっそのこと左から順に１～８の番号付けすることをやめてしまい、「Ａの入っている場所を１とする」としてもいいわけです。それならそもそも「Ａを一番左に入れてしまう」ことになんら一般性を欠かない、という考えに至るわけです。

ということで、Ａを一番左に固定する理由がわかっていただけるでしょうか？
ちなみにＡを一番左に固定する場合、
・Ａの相手・・・７通り
・１回勝てば（ＡもしくはＡに勝ったチーム）と準決勝であたるチームを２つ選ぶ・・・6C2=15通り
・残り４つについて、２つずつにわける・・・4C2÷2=3通り
よって、7*15*3＝315通りとしてもよいでしょう。

ちなみに、７チームのトーナメント戦で、１チームだけ１回戦不戦勝のあるトーナメントの形もまさに上と同じ考えで315通りとなります。

※絵的に考えるなら、
・Ａが右半分にあるトーナメントの場合、左右４チームずつ入れ替えても対戦カードは変わらない（→Ａは左半分にあるとしてよい）
・Ａは左から３，４番目にある場合、左から（１２）と（３４）番目を入れ替えても対戦カードは変わらない（→Ａは左から１，２のどちらかにあるとしてよい）
・Ａが左から２番目にある場合、左から１番目と２番目を入れ替えても対戦カードは変わらない
ということからＡを一番左にあるとしても問題ないことがわかると思います。

。。。これでわかってもらえるでしょうか？

この回答へのお礼

＞ということで、Ａを一番左に固定する理由がわかっていただけるでしょうか？

お返事どうもありがとうございます。わかりました！！なるほど、そういうことだったんですね。「先攻、後攻の区別や、１回戦４試合、２回戦２試合の試合の順序は考えないものとする。」を正確に理解すればそういう結論に達することがとてもよくわかりました。

＞。。。これでわかってもらえるでしょうか？

はい！とてもよくわかりました！！喉に突っかかっていた小骨がとれたようなすっきりした気持ちです。感動しました！どうもありがとうございました！！

お礼日時：2001/10/26 02:03

No.6 回答者： HitomiKurose 回答日時： 2001/10/26 16:53

簡単にするためA,B,C,Dの４チームの場合を考えましょう。

上に一般的なトーナメントの山（？）が乗っていると思ってください。
ABCD
ABDC
BACD
BADC
CDAB
DCAB
CDBA
CDAB
の８つは全て同じ組み合わせになっています。
つまり実質的に
ABCD
ACBD
ADBC
の３通りしかないわけです。

この回答へのお礼

ご回答ありがとうございます。実際に書き出して考えてみると、頭で考えていたものがはっきりと見えてきますね。これを発展させて、８つのトーナメントでも同じように考えたいと思います。どうもありがとうございました。

お礼日時：2001/10/26 23:35

No.5 回答者： kony0 回答日時： 2001/10/26 01:53

言い忘れました。

７チームだとすべての場所が対称ではないのでＡを一番左にすると決めつけてはいけません。
８チームの対戦ですべての場所が対称だからこそできる芸当です。

No.3 回答者： seian 回答日時： 2001/10/25 10:34

解説では、まず1回戦の4試合の対戦相手を決めています。

つまり8チームを2チームずつの4組に分けるわけ方を数えているわけです。
解説ではその所をシンプルに考えているわけですが、この考え方が
分かりづらいのであれば次のようにも考えられます。
まず、
8チームの中から2チームを選ぶ：8C2
残り6チームから2チームを選ぶ：6C2
残り6チームから2チームを選ぶ：4C2
2チームが残るからこれで4チームに分かれた。
場合の数は8C2*6C2*4C2
ただしこれではa組、b組、・・というように4つの組を区別して
考えた事になるのでこの分：4!だけ数えすぎ。
よって、8チームを2チームずつの4組に分けるわけ方は
8C2*6C2*4C2/4!=105
2回戦以降については同様です。

全く反対に、まず、すべて先攻後攻を考えたトーナメント表を考えて、
そこから出発するやり方も可能です。
トーナメントの表の1回戦の8つの空欄に8チームを割り当てればよいのですから8!通り。
ここで問題では先攻後攻、試合の順番は考えないと言っていますのでこの分を評価すればいいわけです。
8チームのトーナメントですから決勝まで7試合、先攻後攻、試合の順番は考えないということは、
トーナメント表の各対戦において左右(先攻後攻)を考えないというのに等しいので
結局場合の数は：8!/2^7=315

この回答へのお礼

＞解説では、まず1回戦の4試合の対戦相手を決めています。
つまり8チームを2チームずつの4組に分けるわけ方を数えているわけです。
解説ではその所をシンプルに考えているわけですが、この考え方が
分かりづらいのであれば次のようにも考えられます。


お返事ありがとうございます。いくら考えてみてもよくわからないので、紹介してくださった方法で考えようかと思います。

＞8チームのトーナメントですから決勝まで7試合、先攻後攻、試合の順番は考えないということは、
トーナメント表の各対戦において左右(先攻後攻)を考えないというのに等しいので

さらに別の方法も教えてくださってどうもありがとうございます。そこで、ちょっとわからないところがあったのですが、「トーナメント表の各対戦において左右(先攻後攻)を考えないというのに等しいので 」この部分で2^7で割るということになるのはわかるのですが、これは先攻後攻の順序だけを考えないようにしているだけですよね。これとは、べつに、試合の順序を考えないようにするためには、もう一回2^7で割らなければ行けないのではないのでしょうか。多分私の思い違いだと思いますが。

お礼日時：2001/10/26 00:24

No.2 回答者： kony0 回答日時： 2001/10/25 00:54

Ａを混同していませんか？

回答では、Ａというのは一貫してチーム名のことですが、
s-wordさんが「Ａの位置にくる文字」と言っているところからして、
トーナメント表の一番左（いわゆる１回戦目の先攻）の「場所」のことをＡと思っていて、そこに入るチームを８チームの中から選ぶ、という考えをされているのではないでしょうか？

「先攻、後攻の区別や、１回戦４試合、２回戦２試合の試合の順序は考えないものとする」と言っていることから、Ａチームをはじめにトーナメント表の一番左に入れても、なんら一般性を失うことはない、という意味なのです。

これで解決となるでしょうか？

ちなみに、トーナメント表の組み合わせを考えるにあたっては、解答の方法がいいと思うのですが、別解。

まず８チームを、４チームずつにわけます。つまりトーナメント表の左半分と右半分に入るチームに分けるということ。
このとき、左に入る４チームを選べば自動的に右半分に入るチームも決まりますが、特に注意するのは、（１２３４）を選ぶ（左半分に入れる）のと（５６７８）を選ぶのとは結局同じ結果であることに注意して、8C4÷2=35通り

これは所謂「８人を４人部屋Ａ、Ｂに分けるのと、４人ずつのグループに分ける」ことの違いと同じです。（後者にあたる）

で、４チームずつにわけたそれぞれについて、４チームを２チーム×２に分ける分け方は、先ほどと全く同様に4C2÷2=3通りずつ。（特定のチームと対戦するのは誰か３通りから選べば、残りの対戦も勝手に決まる）

よって、35*3*3＝305通り

この回答へのお礼

＞Ａを混同していませんか？
回答では、Ａというのは一貫してチーム名のことですが、
s-wordさんが「Ａの位置にくる文字」と言っているところからして、
トーナメント表の一番左（いわゆる１回戦目の先攻）の「場所」のことをＡと思っていて、そこに入るチームを８チームの中から選ぶ、という考えをされているのではないでしょうか？

はい、そのように考えていました。

＞「先攻、後攻の区別や、１回戦４試合、２回戦２試合の試合の順序は考えないものとする」と言っていることから、Ａチームをはじめにトーナメント表の一番左に入れても、なんら一般性を失うことはない、という意味なのです。

これで解決となるでしょうか？

すいません、Ａチームをはじめにトーナメント表の一番左に決める理由がわからないのですが。トーナメント方式の組み合わせを求める時のパターンなのでしょうか。どういった考え方から出てきているのでしょうか。Aだけでなく、左から数えて、CやEの位置にも初めから、ここにくると決めてしまっていますよね。ちょっととん拍子もない考え方だと思うのですが。

＞ちなみに、トーナメント表の組み合わせを考えるにあたっては、解答の方法がいいと思うのですが、別解。

別解まで紹介していただいてありがとうございます。こちらのほうは、よく理解できました。ありがとうございました。

お礼日時：2001/10/26 00:16

No.1 回答者： pei-pei 回答日時： 2001/10/24 20:48

> 肝心のAの位置にくる文字を選ぶ８通りがはずれてしまっているように思えるのですが。

　「Aの位置にくる文字」というのは、例えば
「トーナメント表の右端にどのチームがくるか？」
という意味でしょうか？　そうだとすれば、問題文に
「ただし、先攻、後攻の区別や、１回戦４試合、２回戦２試合の試合の順序は考えないものとする。」
とあるので、それは数えなくていいんですよ。
　トーナメント表上の位置は、試合の順序や先行・後攻を意味するわけですから。
純粋に対戦相手の組み合わせを考える問題なのです。

この回答へのお礼

ご回答ありがとうございます。なるほど、その問題文の条件に注目すればよいのですね。8C6・4C2 のように対戦する組み合わせを考えれば、問題の条件とかみ合わなくなってしまいますよね。

＞純粋に対戦相手の組み合わせを考える問題なのです。

ここをもうちょっと解説していただきたいのですが、対戦相手の決め方の通りが、この問題の答えになるという翻訳が理解できません。どのように考えればスムーズに考えられますでしょうか。

お礼日時：2001/10/25 00:20