Difference between revisions of "1999 AIME Problems/Problem 13"
m |
m (fmtting) |
||
| 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>50 \%</math> chance of winning any game it plays. The probability that no two teams win the same number of games is <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 == | ||
Now one team must win 0 games, one team must win one game, ... , and one team must win all 39 games it plays. Now let's assume that team one wins all games, ... , and team 40 loses all games. The probability that team 40 wins all games is <math>\dfrac{1}{2^{39}}</math>. Now that team 39 has lost it's game, it has a probability of <math>\dfrac{1}{2^{38}}</math> of winning all of the other games. So on, until we get | Now one team must win 0 games, one team must win one game, ... , and one team must win all 39 games it plays. Now let's assume that team one wins all games, ... , and team 40 loses all games. The probability that team 40 wins all games is <math>\dfrac{1}{2^{39}}</math>. Now that team 39 has lost it's game, it has a probability of <math>\dfrac{1}{2^{38}}</math> of winning all of the other games. So on, until we get | ||
| − | < | + | <cmath>\frac{1}{2^{39+38+\cdots+1}} = \frac{1}{2^{780}}</cmath> |
But that was assuming that we knew which team got what score. Now we need to account of the permutations of each team: | But that was assuming that we knew which team got what score. Now we need to account of the permutations of each team: | ||
| − | < | + | <cmath>\dfrac{40!}{2^{780}}</cmath> |
| − | Now we need to find how many 2's there are in 40! . There are | + | Now we need to find how many <math>2</math>'s there are in <math>40!</math>. There are |
| − | < | + | <cmath>\left\lfloor \dfrac{40}{2} \right\rfloor +\left\lfloor\dfrac{40}{4} \right\rfloor +\left\lfloor\dfrac{40}{8} \right\rfloor +\left\lfloor\dfrac{40}{16} \right\rfloor +\left\lfloor\dfrac{40}{32} \right\rfloor = 38</cmath> |
Therefore, | Therefore, | ||
| − | < | + | <cmath>n=2^{780-38}=2^{742}</cmath> |
and | and | ||
| − | < | + | <cmath>\log_{2} n =\boxed{742}</cmath> |
== See also == | == See also == | ||
Revision as of 17:13, 28 October 2007
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
Now one team must win 0 games, one team must win one game, ... , and one team must win all 39 games it plays. Now let's assume that team one wins all games, ... , and team 40 loses all games. The probability that team 40 wins all games is 
. Now that team 39 has lost it's game, it has a probability of 
of winning all of the other games. So on, until we get
![\[\frac{1}{2^{39+38+\cdots+1}} = \frac{1}{2^{780}}\]](http://latex.artofproblemsolving.com/9/4/c/94c8eb78a1b6b57da7a8d32e0dfa71d6b611feee.png)
But that was assuming that we knew which team got what score. Now we need to account of the permutations of each team:
![\[\dfrac{40!}{2^{780}}\]](http://latex.artofproblemsolving.com/6/0/d/60de9864e22a8be518cf922459d9848ada2c4884.png)
Now we need to find how many 
's there are in 
. There are
![\[\left\lfloor \dfrac{40}{2} \right\rfloor +\left\lfloor\dfrac{40}{4} \right\rfloor +\left\lfloor\dfrac{40}{8} \right\rfloor +\left\lfloor\dfrac{40}{16} \right\rfloor +\left\lfloor\dfrac{40}{32} \right\rfloor = 38\]](http://latex.artofproblemsolving.com/3/3/e/33eae7cc376800ed0dccbc6288dac19dd54ddb3c.png)
Therefore,
![\[n=2^{780-38}=2^{742}\]](http://latex.artofproblemsolving.com/b/6/a/b6a4bf0697aa4689a9bf65a69e80ebb07bfffc7d.png)
and
![\[\log_{2} n =\boxed{742}\]](http://latex.artofproblemsolving.com/8/7/4/874fc014a4d42ff83455a034481b4595a85f7ea2.png)
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 | ||
