1999 AIME Problems/Problem 13
Forty teams play a tournament in which every team plays every other team exactly once. No ties occur, and each team has a chance of winning any game it plays. The probability that no two teams win the same number of games is where and are relatively prime positive integers. Find
There are total pairings of teams, and thus possible outcomes. In order for no two teams to win the same number of games, they must each win a different number of games. Since the minimum and maximum possible number of games won are 0 and 39 respectively, and there are 40 teams in total, each team corresponds uniquely with some , with , where represents the number of games the team won. With this in mind, we see that there are a total of outcomes in which no two teams win the same number of games. Further, note that these are all the valid combinations, as the team with 1 win must beat the team with 0 wins, the team with 2 wins must beat the teams with 1 and 0 wins, and so on; thus, this uniquely defines a combination.
The desired probability is thus . We wish to simplify this into the form , where and are relatively prime. The only necessary step is to factor out all the powers of 2 from ; the remaining number is clearly relatively prime to all powers of 2.
The number of powers of 2 in is
|1999 AIME (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15|
|All AIME Problems and Solutions|