数学の質問です。 高校数学得意な人！お願いします！ 8人のトーナメント戦の組み合わせは何通りか とい

数学の質問です。　高校数学得意な人！お願いします！

8人のトーナメント戦の組み合わせは何通りか

という問題で、解答は1回戦が105通り、2回戦が3通り、決勝が1通りで105×3×1＝315通りとなっています。

これだと、1回戦に誰が勝ち上がるかを考慮していない気がするのですが、なぜこの計算で良いのかを解説していただきたいです。

No.5 回答者： ありものがたり 回答日時： 2023/07/01 14:37

何で１回戦から順に考えていくかな？

まずは全体を準決勝第1試合目指して戦う4人と
準決勝第2試合目指して戦う4人に分ける。
その分け方が、(8C4)/2! 通り。
それぞれのブロックを同じ準々決勝目指して戦う2人づつに分けると、
どちらのブロックも (4C2)/2! 通りづつ。
対戦の組み方は、全部で { (8C4)/2! }・{ (4C2)/2! }² = (35)・(3)² = 315 通り。

No.4 回答者： stomachman 回答日時： 2023/06/30 09:27

樹状のトーナメント表をまず作る。

たとえば上が根元=決勝戦になるように描いて、葉の数がちょうど参加人数Nと同じになるようにする。
　試合数は(N-1)である。（∵ トーナメントなので、終わってみれば一度も負けていないのは1人だけ（優勝者）で、他の(N-1)人の参加者はそれぞれちょうど1回だけ負けている。1つの試合で負けるのは1人だから、試合数は(N-1)。）

さて、

[A] 試合の2者の組み合わせに（たとえば「先攻・後攻」のような）区別がある場合：
　どの葉に割り当てられるかによって、状況（勝ち進んだ時の各試合の先攻・後攻）が全部異なる。
　つまり、N個あるそれぞれ意味の違う葉に参加者を割り当てるのだから、組み合わせはN!通り。
　トーナメント表がどんな形をしていても、この答は同じ。

[B] 試合の2者の組み合わせに「先攻・後攻」のような区別がなく、かつ、トーナメント表が完全に対称で、どの葉に割り当てられたとしても、優勝するまでに勝つ必要がある試合数が同じである場合（もちろん、Nは2のべき乗でなくてはならない）：
　N個ある葉に参加者を割り当てるとN!通り。しかし、トーナメント表のどの試合についても、右にある枝と左にある枝は対称。すなわち、両者を入れ替えても、実質何も変わらない。（割り当てをやったあとで入れ替えをしても、それは単に、表の描き方が違うだけだ。）
　なので、割り当てを一つ決めたとして、それを「実質何も変わらない」ように入れ替える入れ替え方が2^(N-1)通りある。つまりN!というのは実質同じである割り当て方を重複して数えている。そして、実質が異なる割り当て方の数はN!/2^(N-1)通り。

● たとえば[B]でN=8の場合なら、N!=40320, 2^(N-1)=128、N!/(2^(N-1))=315。
　問題文は不明確だが、どうやら（コタエから察するに）この場合を意図していたのだと思われる。（1回戦、2回戦、… に分けて数える必要はない。）

[C] 試合の2者の組み合わせに「先攻・後攻」のような区別がなく、かつ、トーナメント表が完全には対称でない場合。（すなわち、葉によって、優勝するまでに勝つ必要がある試合数が異なるものがある。）
　この場合はややこしい。具体的にトーナメント表の形を決めた上で、対称性（実質的な意味がない入れ替え方）の数を調べて、参加者を葉へ割り当てるN!通りの割り当て方のうちにどれだけの重複があるかを計算する必要がある。
　たとえば「一度に1試合。勝ち残ったやつに次の挑戦者が掛かっていく」という形のトーナメント表の場合なら、初戦の2つの葉は対称（入れ替えても同じ）だが、他の全ての葉は入れ替えが利かないので、答は N!/2 通り。

No.3 回答者： Tacosan 回答日時： 2023/06/30 00:08

「トーナメント戦の組み合わせ」という言葉の解釈の問題だね. でも, ふつうは「1回戦に誰が勝ち上がるか」は考慮しないと思う. そこは「数学」の話ではないので, 「高校数学得意な人！お願いします！」と呼び掛けても意味はない.

なおもっと突っ込んでいいなら「『トーナメント戦』とはどのようなものなのか」まで議論になるところ. 「8人のトーナメント」だからといって「シードを絶対に発生させてはならない」とはいいきれないし, もっと極端な場合として「ステップラダーは『トーナメント戦』なのか」とか考えだすとややこしい.

いずれにしても本来の「トーナメント」ではないんだけど....

No.2 回答者： ssawatake 回答日時： 2023/06/29 21:43

ミスプリじゃ無いですよ。

第1試合で誰と対戦するかは、8人を2人ずつ4組に分ければよい。
この4組は区別が出来ないことに注意すると、
(8C2×6C2×4C2×2C2)/(4！)＝105通り。

第1試合の勝者は4人。
この4人が誰と対戦するかは、4人を2人ずつ2組に分けるので、
(4C2×2C2)/(2！)＝3通り。

第2試合の勝者は2人しかいないので、1通り。

以上より、トーナメントの組み合わせ方式は
105×3×1＝315通り。

>>1回戦に誰が勝ち上がるかを考慮していない気がする
考慮してるから、105×・・・となってます。

105通りの各々に勝者が4人でてくるので、
105×(第2試合の組み合わせ）で計算してるワケ。

No.1 回答者： kairou 回答日時： 2023/06/29 21:37

＞解答は1回戦が105通り、2回戦が3通り、決勝が1通り

これは 変ですね。ミスプリントにしては 差が大きすぎる。
何か 別の条件は ありませんか。

1回戦 : 8人で2人づつの組み合わせは ₈C₂=28 で 28通りです。
2回戦 : 4人で 2人づつの組み合わせは ₄C₂=6 で 6通りです。
決勝戦　：当然 2人の対決ですから 1通りです。
合わせて 28+6+1=35 で 35通りです。

実際の試合数は 1回戦が4試合、2回戦が2試合、決勝が1試合で、
合計 7試合です。