Difference between revisions of "1999 AIME Problems/Problem 13"
m |
(→Solution) |
||
| (13 intermediate revisions by 5 users not shown) | |||
| Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
| − | Forty teams play a tournament in which every team plays every other team exactly once. No ties occur, and each team has a <math> | + | Forty teams play a tournament in which every team plays every other team exactly once. No ties occur, and each team has a <math>50 \%</math> chance of winning any game it plays. The [[probability]] that no two teams win the same number of games is <math>\frac mn,</math> where <math>m_{}</math> and <math>n_{}</math> are [[relatively prime]] positive integers. Find <math>\log_2 n.</math> |
| − | == Solution == | + | ==Solution== |
| + | |||
| + | There are <math>{40 \choose 2} = 780</math> total pairings of teams, and thus <math>2^{780}</math> 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 <math>k</math>, with <math>0 \leq k \leq 39</math>, where <math>k</math> represents the number of games the team won. With this in mind, we see that there are a total of <math>40!</math> 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 <math>\frac{40!}{2^{780}}</math>. We wish to simplify this into the form <math>\frac{m}{n}</math>, where <math>m</math> and <math>n</math> are relatively prime. The only necessary step is to factor out all the powers of 2 from <math>40!</math>; the remaining number is clearly relatively prime to all powers of 2. | ||
| + | |||
| + | |||
| + | The number of powers of 2 in <math>40!</math> is <math>\left \lfloor \frac{40}{2} \right \rfloor + \left \lfloor \frac{40}{4} \right \rfloor + \left \lfloor \frac{40}{8} \right \rfloor + \left \lfloor \frac{40}{16} \right \rfloor + \left \lfloor \frac{40}{32} \right \rfloor = 20 + 10 + 5 + 2 + 1 = 38.</math> | ||
| + | |||
| + | |||
| + | <math>780-38 = \boxed{742}</math>. | ||
== See also == | == See also == | ||
| − | + | {{AIME box|year=1999|num-b=12|num-a=14}} | |
| − | + | ||
| − | + | [[Category:Intermediate Combinatorics Problems]] | |
| + | {{MAA Notice}} | ||
Latest revision as of 00:38, 6 October 2015
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. 
