CODEWITHSUNDEEP
algorithm
Leonardo Lopez
Leonardo Lopez

Reputation: 1143

Tennis Tournament Pairing (1x3x5x7x9x...(2n-1) )

Need help with this algorithm problem: In a tennis tournament game we have 2n players. in the first round, each player only plays once, therefore we have n games, each game with 2 players. Show that the pairing of players for the first round can be done precisely with 1 x 3 x 5 x 7 x 9 ... (2n-1).

It looks as though it's factorial, but with odd numbers. All I read about factorials never come to this conclusion, and in a combination problem, sources only explain the possible pairings on a 1 on 1 ratio, not a 2 on 1, as it is in this case (2 players per game). Reading and reading has gotten me nowhere.

Upvotes: 1

Views: 3022

Answers (2)

ThomasMcLeod
ThomasMcLeod

Reputation: 7769

This answer illustrates an inductive proof of the number of tournaments t over a set of n pairs of vertices. For a simpler, direct counting approach, see Daniel Fischer's answer.

I use strong induction to show t( n ) = (2 n - 1)!!.

For a basis, let n = 1. So we have t(1) = (2 - 1)!! = 1. Since there can be only 1 tournament with 1 pair of players, the basis checks.

Next, we assume that t = (2 m - 1)!! for all m < n and we let i + 1 = n. We start with a tournament of i pairs, add a new pair to make n pairs, and show that t( n ) = (2 n - 1)!!. There are two cases to consider. Case 1: the new pair plays against itself, and case 2:, it doesn't. Since the two cases are mutually exclusive, we can determine the number of tournaments generated by each case separately and add the results.

Considering case 1, how many ways can we match the new pair to the existing players? Well, the first player of the new pair can play any 2 i existing players and the second player can play any 2 i - 1 remaining players. Hence the total number of match-ups of the new pair is 2 i (2 i - 1). Of course after we match the new pair we cannot forget there are i - 1 pairs left. By the inductive hypothesis, we can match these players (2 (i - 1) - 1)!! ways. After applying the product rule for counting, the result for case 1 is 2 i (2 i - 1) (2 (i - 1) - 1)!!.

Turning to case 2, the new pair can play itself 1 way. By the inductive hypothesis the remaining i pairs can form a tournament (2 i - 1)!! ways, so the total for case 2 is (2 i - 1)!!.

Adding the two cases together we have t( n ) = 2 i (2 i - 1) (2 (i - 1) - 1)!! + (2 i - 1)!!.

We factor out a (2 (i - 1) - 1)!! on the right side to get t( n ) = (2 (i - 1) - 1)!! (2 i (2 i - 1) + (2 i - 1)).

Combining like terms we have t( n ) = (2 (i - 1) - 1)!! (2 i - 1)(2 i + 1).

Folding the trailing factors into the double factorial we have t( n ) = (2 (i + 1) - 1)!!

Finally, we apply the definition of i and we have t( n ) = (2 n - 1)!!

Upvotes: 1

Daniel Fischer
Daniel Fischer

Reputation: 183918

Obvoiusly, for n = 1, there is exactly one way to pair the two players.

Now, inductively, player 1 can be paired with 2*n - 1 players, and the remaining 2*(n-1) players can then be paired in

1*3*...*(2*n-3)

ways by the induction hypothesis, for a total of 1*3*...*(2*n-3)*(2*n-1) ways.

Upvotes: 1

Related Questions