16人トーナメントの組み方は？
松谷です。
16人トーナメントの組み方は何通りか？
小学生部の授業中に、中学生から質問されて結構適当に答えてしまったので懺悔のためにブログにしておきます。
まず、ちょっと多すぎるので少ない4人のトーナメントから確認します。
こんなトーナメントがあって、この表の見え方として、何通りありますか？
と聞かれたら、もちろん4!通りです。(4×3×2×1=24通り)
4人の並び方ですから。
でも、本質的なトーナメントの組み合わせとして、
などなどは同じですね(試合順序を考慮しなければ)。①と②が一回戦で対戦して、③と④が一回戦で対戦して、勝者同士が決勝で対戦するという感じですからね。
ということで、こういうときに、オススメの考え方がありました。
それは、1人に注目するというやり方です。
①はトーナメントのどっかにいるわけなので、それを例えば左端に固定して、その対戦相手などを考えていくというやり方です。
そうすると、①の対戦相手は、残りの3人のうち1人を選ぶということで、3通りです。①がいる側の2人を決めてしまえば、残りは自動的に決まります。ということで、全部で3通りというわけですね。
ということで、ちょっと多いですが、16人バージョンをやってみましょうか。
しかし、もう面倒になってきたので、表で一気に書いてしまいます。。。
まずは、注目する1人を決めます(①の人)。その対戦相手として、残りの15人から1人選びます。15C1。
次に、①のペアの勝者と二回戦で対戦する人を2人決めます。14C2。
その次に、①が勝った場合に3回戦で対戦する可能性がある4人を選びます。12C4。しかし、その4人の中のトーナメントとして、3C1=3通りあります。
これで、あと残り8人になりましたので、逆側のトーナメントの8人を決めていきます。
残った8人を改めてa,b,c,d,e,f,g,hとしてみましょう。そうしたら、aは必ずどっかにいるわけなので、aに注目して左端に固定します。
そして、aの対戦相手を残り7人から選びます。7C1。
そして、aが2回戦で対戦しうる2人を選びます。6C2。
あとは、4人残ってますが、この組み方は3C1で3通りでした。
ということで、全部かけると、
15C1×14C2×12C4×3C1×7C1×6C2×3C1=
なんと、
638512875通り！！
なんと、ルフィもびっくり6億超えですよ！
ひー。32ドローのトーナメント表なんか作った日にゃーまあほぼ確実に毎回違うものになりますねー。一期一会ですねー？
(ちなみに、他にもいろんな考え方で、出せますから気になる人は独習数学を読んでくださいね！
もしかしたら、一般化して考えたい場合は、次の方法が便利かもしれません。
2^n人の順列は(2^n)!通り。トーナメントの組み合わせを考えるうえでは各試合で左右の区別は不要。
ここで、試合数について考えると、1試合につき1人が負けていくので、優勝を決めるまでには、2^n-1試合あるとわかる。よって、組み合わせパターンは(2^n)!/2^(2^n-1)通りとなる。
n=4(16人)であれば16!/2^15=638512875と計算できる。)