Difference between revisions of "2006 AIME II Problems/Problem 10"

m (Solution)
(simpler solution)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
Seven teams play a soccer tournament in which each team plays every other team exactly once. No ties occur, each team has a <math> 50\% </math> chance of winning each game it plays, and the outcomes of the games are independent. In each game, the winner is awarded a point and the loser gets 0 points. The total points are accumilated to decide the ranks of the teams. In the first game of the tournament, team <math> A </math> beats team <math> B. </math> The probability that team <math> A </math> finishes with more points than team <math> B </math> is <math> m/n, </math> where <math> m </math> and <math> n </math> are relatively prime positive integers. Find <math> m+n. </math>
+
Seven teams play a soccer tournament in which each team plays every other team exactly once. No ties occur, each team has a <math> 50\% </math> chance of winning each game it plays, and the outcomes of the games are independent. In each game, the winner is awarded a point and the loser gets 0 points. The total points are accumilated to decide the ranks of the teams. In the first game of the tournament, team <math> A </math> beats team <math> B. </math> The [[probability]] that team <math> A </math> finishes with more points than team <math> B </math> is <math> m/n, </math> where <math> m </math> and <math> n </math> are relatively prime positive integers. Find <math> m+n. </math>
  
 +
__TOC__
 
== Solution ==
 
== Solution ==
 +
=== Solution 1 ===
 +
The results of the five remaining games are independent of the first game, so by symmetry, the probability that <math>A</math> scores higher than <math>B</math> in these five games is equal to the probability that <math>B</math> scores higher than <math>A</math>. We let this probability be <math>p</math>; then the probability that <math>A</math> and <math>B</math> end with the same score in these give games is <math>1-2p</math>.
 +
 +
Of these three cases (<math>|A| > |B|, |A| < |B|, |A|=|B|</math>), the last is the easiest to calculate (see solution 2 for a way to directly calculate the other cases).
 +
 +
There are <math>{6\choose k}</math> ways to <math>A</math> to have <math>k</math> victories, and <math>{6\choose k}</math> ways for <math>B</math> to have <math>k</math> victories. Summing for all values of <math>k</math>,
 +
<center><math>1-2p = \frac{1}{2^{5} \times 2^{5}}\left(\sum_{k=0}^{5} {6\choose k}^2\right) = \frac{1^2+5^2+10^2+10^2+5^2+1^2}{1024} = \frac{126}{512}.</math></center>
 +
Thus <math>p = \frac 12 \left(1-\frac{126}{512}\right) = \frac{193}{512}</math>. The desired probability is the sum of the cases when <math>|A| \ge |B|</math>, so the answer is <math>\frac{126}{512} + \frac{193}{512} = \frac{319}{512}</math>, and <math>m+n = \boxed{831}</math>.
 +
 +
=== Solution 2 ===
 
You can break this into cases based on how many rounds A wins out of the remaining 5 games.
 
You can break this into cases based on how many rounds A wins out of the remaining 5 games.
  
If A wins 0 games, then B must win 0 games and the probability of this is <math> \frac{{5 \choose 0}}{2^5} \frac{{5 \choose 0}}{2^5} = \frac{1}{1024} </math>.
+
If <math>A</math> wins 0 games, then <math>B</math> must win 0 games and the probability of this is <math> \frac{{5 \choose 0}}{2^5} \frac{{5 \choose 0}}{2^5} = \frac{1}{1024} </math>.
  
If A wins 1 games, then B must win 1 or less games and the probability of this is <math> \frac{{5 \choose 1}}{2^5} \frac{{5 \choose 0}+{5 \choose 1}}{2^5} = \frac{30}{1024} </math>.
+
If <math>A</math> wins 1 games, then <math>B</math> must win 1 or less games and the probability of this is <math> \frac{{5 \choose 1}}{2^5} \frac{{5 \choose 0}+{5 \choose 1}}{2^5} = \frac{30}{1024} </math>.
  
If A wins 2 games, then B must win 2 or less games and the probability of this is <math> \frac{{5 \choose 2}}{2^5} \frac{{5 \choose 0}+{5 \choose 1}+{5 \choose 2}}{2^5} = \frac{160}{1024} </math>.
+
If <math>A</math> wins 2 games, then <math>B</math> must win 2 or less games and the probability of this is <math> \frac{{5 \choose 2}}{2^5} \frac{{5 \choose 0}+{5 \choose 1}+{5 \choose 2}}{2^5} = \frac{160}{1024} </math>.
  
If A wins 3 games, then B must win 3 or less games and the probability of this is <math> \frac{{5 \choose 3}}{2^5} \frac{{5 \choose 0}+{5 \choose 1}+{5 \choose 2}+{5 \choose 3}}{2^5} = \frac{260}{1024} </math>.
+
If <math>A</math> wins 3 games, then <math>B</math> must win 3 or less games and the probability of this is <math> \frac{{5 \choose 3}}{2^5} \frac{{5 \choose 0}+{5 \choose 1}+{5 \choose 2}+{5 \choose 3}}{2^5} = \frac{260}{1024} </math>.
  
If A wins 4 games, then B must win 4 or less games and the probability of this is <math> \frac{{5 \choose 4}}{2^5} \frac{{5 \choose 0}+{5 \choose 1}+{5 \choose 2}+{5 \choose 3}+{5 \choose 4}}{2^5} = \frac{155}{1024} </math>.
+
If <math>A</math> wins 4 games, then <math>B</math> must win 4 or less games and the probability of this is <math> \frac{{5 \choose 4}}{2^5} \frac{{5 \choose 0}+{5 \choose 1}+{5 \choose 2}+{5 \choose 3}+{5 \choose 4}}{2^5} = \frac{155}{1024} </math>.
  
If A wins 5 games, then B must win 5 or less games and the probability of this is <math> \frac{{5 \choose 5}}{2^5} \frac{{5 \choose 0}+{5 \choose 1}+{5 \choose 2}+{5 \choose 3}+{5 \choose 4}+{5 \choose 5}}{2^5} = \frac{32}{1024} </math>.
+
If <math>A</math> wins 5 games, then <math>B</math> must win 5 or less games and the probability of this is <math> \frac{{5 \choose 5}}{2^5} \frac{{5 \choose 0}+{5 \choose 1}+{5 \choose 2}+{5 \choose 3}+{5 \choose 4}+{5 \choose 5}}{2^5} = \frac{32}{1024} </math>.
  
Summing these 6 cases, we get <math> \frac{638}{1024} </math>, which simplifies to <math> \frac{319}{512} </math>, so our answer is <math>319 + 512 = 831</math>.
+
Summing these 6 cases, we get <math> \frac{638}{1024} </math>, which simplifies to <math> \frac{319}{512} </math>, so our answer is <math>319 + 512 = \boxed{831}</math>.
  
 
== See also ==
 
== See also ==

Revision as of 21:57, 25 April 2008

Problem

Seven teams play a soccer tournament in which each team plays every other team exactly once. No ties occur, each team has a $50\%$ chance of winning each game it plays, and the outcomes of the games are independent. In each game, the winner is awarded a point and the loser gets 0 points. The total points are accumilated to decide the ranks of the teams. In the first game of the tournament, team $A$ beats team $B.$ The probability that team $A$ finishes with more points than team $B$ is $m/n,$ where $m$ and $n$ are relatively prime positive integers. Find $m+n.$

Solution

Solution 1

The results of the five remaining games are independent of the first game, so by symmetry, the probability that $A$ scores higher than $B$ in these five games is equal to the probability that $B$ scores higher than $A$. We let this probability be $p$; then the probability that $A$ and $B$ end with the same score in these give games is $1-2p$.

Of these three cases ($|A| > |B|, |A| < |B|, |A|=|B|$), the last is the easiest to calculate (see solution 2 for a way to directly calculate the other cases).

There are ${6\choose k}$ ways to $A$ to have $k$ victories, and ${6\choose k}$ ways for $B$ to have $k$ victories. Summing for all values of $k$,

$1-2p = \frac{1}{2^{5} \times 2^{5}}\left(\sum_{k=0}^{5} {6\choose k}^2\right) = \frac{1^2+5^2+10^2+10^2+5^2+1^2}{1024} = \frac{126}{512}.$

Thus $p = \frac 12 \left(1-\frac{126}{512}\right) = \frac{193}{512}$. The desired probability is the sum of the cases when $|A| \ge |B|$, so the answer is $\frac{126}{512} + \frac{193}{512} = \frac{319}{512}$, and $m+n = \boxed{831}$.

Solution 2

You can break this into cases based on how many rounds A wins out of the remaining 5 games.

If $A$ wins 0 games, then $B$ must win 0 games and the probability of this is $\frac{{5 \choose 0}}{2^5} \frac{{5 \choose 0}}{2^5} = \frac{1}{1024}$.

If $A$ wins 1 games, then $B$ must win 1 or less games and the probability of this is $\frac{{5 \choose 1}}{2^5} \frac{{5 \choose 0}+{5 \choose 1}}{2^5} = \frac{30}{1024}$.

If $A$ wins 2 games, then $B$ must win 2 or less games and the probability of this is $\frac{{5 \choose 2}}{2^5} \frac{{5 \choose 0}+{5 \choose 1}+{5 \choose 2}}{2^5} = \frac{160}{1024}$.

If $A$ wins 3 games, then $B$ must win 3 or less games and the probability of this is $\frac{{5 \choose 3}}{2^5} \frac{{5 \choose 0}+{5 \choose 1}+{5 \choose 2}+{5 \choose 3}}{2^5} = \frac{260}{1024}$.

If $A$ wins 4 games, then $B$ must win 4 or less games and the probability of this is $\frac{{5 \choose 4}}{2^5} \frac{{5 \choose 0}+{5 \choose 1}+{5 \choose 2}+{5 \choose 3}+{5 \choose 4}}{2^5} = \frac{155}{1024}$.

If $A$ wins 5 games, then $B$ must win 5 or less games and the probability of this is $\frac{{5 \choose 5}}{2^5} \frac{{5 \choose 0}+{5 \choose 1}+{5 \choose 2}+{5 \choose 3}+{5 \choose 4}+{5 \choose 5}}{2^5} = \frac{32}{1024}$.

Summing these 6 cases, we get $\frac{638}{1024}$, which simplifies to $\frac{319}{512}$, so our answer is $319 + 512 = \boxed{831}$.

See also

2006 AIME II (ProblemsAnswer KeyResources)
Preceded by
Problem 9
Followed by
Problem 11
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
All AIME Problems and Solutions