Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1999 AIME Problems/Problem 13"

(→‎Solution)
(→‎Solution)
 
(11 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>\displaystyle 50 \%</math> chance of winning any game it plays.  The probability that no two teams win the same number of games is <math>\displaystyle m/n,</math> where <math>\displaystyle m_{}</math> and <math>\displaystyle n_{}</math> are relatively prime positive integers.  Find <math>\displaystyle \log_2 n.</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
 
  
−
<math>\dfrac{1}{2^{39+38+\cdots+1}</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.
  
−
But that was assuming that we knew which team got what score. Now we need to account of the permutations of each team:
 
  
−
<math>\dfrac{40!}{2^{780}}</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.
  
−
Now we need to find how many 2's there are in 40. There are
 
  
−
<math>\lfloor \dfrac{40}{2} \rfloor +\lfloor \dfrac{40}{4} \rfloor +\lfloor \dfrac{40}{8} \rfloor +\lfloor \dfrac{40}{16} \rfloor +\lfloor \dfrac{40}{32} \rfloor = 38</math>
+
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>  
  
−
Therefore,
 
  
−
<math>n=2^{780-38}=2^{742}</math>
+
<math>780-38 = \boxed{742}</math>.
−
 
 
−
and
 
−
 
 
−
<math>\log_{2} n =\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 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 $50 \%$ chance of winning any game it plays. The probability that no two teams win the same number of games is $\frac mn,$ where $m_{}$ and $n_{}$ are relatively prime positive integers. Find $\log_2 n.$

Solution

There are ${40 \choose 2} = 780$ total pairings of teams, and thus $2^{780}$ 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 $k$, with $0 \leq k \leq 39$, where $k$ represents the number of games the team won. With this in mind, we see that there are a total of $40!$ 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 $\frac{40!}{2^{780}}$. We wish to simplify this into the form $\frac{m}{n}$, where $m$ and $n$ are relatively prime. The only necessary step is to factor out all the powers of 2 from $40!$; the remaining number is clearly relatively prime to all powers of 2.


The number of powers of 2 in $40!$ is $\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.$


$780-38 = \boxed{742}$.

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1999_AIME_Problems/Problem_13&oldid=72395"