1999 AIME Problems/Problem 13
Problem
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
Solution
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
.
See also
1999 AIME (Problems • Answer Key • Resources) | ||
Preceded by Problem 12 |
Followed by Problem 14 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.