Difference between revisions of "1999 AIME Problems/Problem 13"
(→Solution) |
(→Solution) |
||
(9 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>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== |
− | |||
− | <math>\ | + | 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. |
− | |||
− | <math>\ | + | 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. |
− | |||
− | <math>\lfloor \ | + | 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> | + | <math>780-38 = \boxed{742}</math>. |
− | |||
− | |||
− | |||
− | |||
== See also == | == See also == | ||
{{AIME box|year=1999|num-b=12|num-a=14}} | {{AIME box|year=1999|num-b=12|num-a=14}} | ||
+ | |||
+ | [[Category:Intermediate Combinatorics Problems]] | ||
+ | {{MAA Notice}} |
Latest revision as of 01: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.