このアルゴリズムの問題について助けが必要です: テニス トーナメント ゲームでは、2n 人のプレーヤーがいます。最初のラウンドでは、各プレイヤーは 1 回だけプレイするため、n ゲームがあり、各ゲームには 2 人のプレイヤーがいます。最初のラウンドのプレーヤーのペアリングが 1 x 3 x 5 x 7 x 9 ... (2n-1) で正確に行えることを示してください。
階乗のように見えますが、奇数です。階乗について私が読んだものはすべてこの結論に達することはなく、組み合わせの問題では、情報源は、この場合のように 2 対 1 ではなく、1 対 1 の比率で可能なペアリングのみを説明しています (ゲームごとに 2 人のプレーヤー)。読書と読書は私をどこにも連れて行きませんでした。
明らかに、 の場合n = 1、2 人のプレーヤーをペアにする方法は 1 つだけです。
ここで、帰納的に、プレイヤー 1 を2*n - 1プレイヤーとペアにすることができ、残りの2*(n-1)プレイヤーをペアにすることができます。
1*3*...*(2*n-3)
方法の合計について、帰納法仮説による1*3*...*(2*n-3)*(2*n-1)方法。
この答えは、頂点のn組のセットに対するトーナメント数tの帰納的証明を示しています。より単純な直接カウント アプローチについては、Daniel Fischer の回答を参照してください。
強い帰納法を使ってt ( n ) = (2 n - 1)!!を示します。
基底として、n = 1 とします。したがって、t (1) = (2 - 1)となります。= 1. 1 ペアのプレイヤーによるトーナメントは 1 つしか存在しないため、ベーシスがチェックされます。
次に、 t = (2 m - 1)と仮定します!! すべての m < n に対して、i + 1 = nとします。iペアのトーナメントから始めて、新しいペアを追加してnペアを作り、t ( n ) = (2 n - 1)!! であることを示します。考慮すべき 2 つのケースがあります。ケース 1:新しいペアはそれ自体に対してプレーし、ケース 2:はそうではありません。2 つのケースは相互に排他的であるため、各ケースで生成されたトーナメントの数を個別に決定し、結果を追加できます。
ケース 1 を考えると、新しいペアを既存のプレーヤーと一致させる方法はいくつありますか? 新しいペアの最初のプレーヤーは任意の 2 i既存のプレーヤーと対戦でき、2 番目のプレーヤーは任意の 2 i - 1 の残りのプレーヤーと対戦できます。したがって、新しいペアの合計マッチアップ数は 2 i (2 i - 1) です。もちろん、新しいペアを一致させた後、i - 1 ペアが残っていることを忘れることはできません。帰納的仮説により、これらのプレーヤーを一致させることができます (2 ( i - 1) - 1)!! 方法。カウントに積規則を適用すると、ケース 1 の結果は 2 i (2 i - 1) (2 ( i - 1) - 1)!! になります。
ケース 2 に目を向けると、新しいペアは 1 つの方法でプレイできます。帰納的仮説により、残りのiペアはトーナメント (2 i - 1) を形成できます!! ケース 2 の合計は (2 i - 1)!! です。
2 つのケースを合計すると、t ( n ) = 2 i (2 i - 1) (2 ( i - 1) - 1) になります!! + (2 i - 1)!!.
(2 ( i - 1) - 1) を因数分解します!! 右側でt ( n ) = (2 ( i - 1) - 1) を取得します!! (2 i (2 i - 1) + (2 i - 1))。
同様の用語を組み合わせると、t ( n ) = (2 ( i - 1) - 1) になります!! (2 i - 1)(2 i + 1)。
後続因子を二重階乗に折りたたむと、t ( n ) = (2 ( i + 1) - 1)!!
最後に、 iの定義を適用すると 、 t ( n ) = (2 n - 1) が得られます!!