Difference between revisions of "1996 AIME Problems/Problem 6"
Mathislife16 (talk | contribs) m (→Problem) |
m (→Solution 2) |
||
(7 intermediate revisions by 2 users not shown) | |||
Line 2: | Line 2: | ||
In a five-team tournament, each team plays one game with every other team. Each team has a <math>50\%</math> chance of winning any game it plays. (There are no ties.) Let <math>\dfrac{m}{n}</math> be the probability that the tournament will produce neither an undefeated team nor a winless team, where <math>m</math> and <math>n</math> are relatively prime integers. Find <math>m+n</math>. | In a five-team tournament, each team plays one game with every other team. Each team has a <math>50\%</math> chance of winning any game it plays. (There are no ties.) Let <math>\dfrac{m}{n}</math> be the probability that the tournament will produce neither an undefeated team nor a winless team, where <math>m</math> and <math>n</math> are relatively prime integers. Find <math>m+n</math>. | ||
− | == Solution == | + | == Solutions == |
+ | |||
+ | === Solution 1 === | ||
+ | |||
We can use [[complementary counting]]: finding the probability that at least one team wins all games or at least one team loses all games. | We can use [[complementary counting]]: finding the probability that at least one team wins all games or at least one team loses all games. | ||
Line 9: | Line 12: | ||
Now we use [[PIE]]: | Now we use [[PIE]]: | ||
− | The probability that one team wins all games is <math>5\cdot (\frac{1}{2})^4=\frac{5}{16}</math>. | + | The probability that one team wins all games is <math>5\cdot \left(\frac{1}{2}\right)^4=\frac{5}{16}</math>. |
Similarity, the probability that one team loses all games is <math>\frac{5}{16}</math>. | Similarity, the probability that one team loses all games is <math>\frac{5}{16}</math>. | ||
− | The probability that one team wins all games and another team loses all games is <math>(5\cdot (\frac{1}{2})^4)(4\cdot (\frac{1}{2})^3)=\frac{5}{32}</math>. | + | The probability that one team wins all games and another team loses all games is <math>\left(5\cdot \left(\frac{1}{2}\right)^4\right)\left(4\cdot \left(\frac{1}{2}\right)^3\right)=\frac{5}{32}</math>. |
<math>\frac{5}{16}+\frac{5}{16}-\frac{5}{32}=\frac{15}{32}</math> | <math>\frac{5}{16}+\frac{5}{16}-\frac{5}{32}=\frac{15}{32}</math> | ||
Line 20: | Line 23: | ||
<math>17+32=\boxed{049}</math> | <math>17+32=\boxed{049}</math> | ||
+ | |||
+ | === Solution 2 === | ||
+ | |||
+ | There are <math>\dbinom{5}{2} = 10</math> games in total, and every game can either end in a win or a loss. Therefore, there are <math>2^{10} = 1024</math> possible outcomes. | ||
+ | |||
+ | Now, computing this probability directly seems a little hard, so let's compute the complement -- the probability that there is an undefeated team, a winless team, or both. | ||
+ | |||
+ | The number of ways that we can have an undefeated team is <math>5 \cdot 2^6,</math> as there are five ways to choose the team itself and <math>2^6</math> outcomes for the games that are not concerning the undefeated team. Reversing all the wins to losses yields a winless team, so this situation is symmetrical to the first one. Therefore, there are <math>5 \cdot 2^6 + 5 \cdot 2^6</math> ways for an undefeated or winless team. | ||
+ | |||
+ | In the process, however, we have accidentally overcounted the scenario of both an undefeated and winless team. There are <math>5 \cdot 4 \cdot 2^3</math> ways for this scenario to happen, because there are five ways to choose the undefeated team, four ways for the winless, and three games that don't concern either of the teams. Therefore, there are <math>5 \cdot 2^6 + 5 \cdot 2^6 - 5 \cdot 4 \cdot 2^3 = 480</math> ways to have an undefeated and/or winless team, so there are <math>1024 - 480 = 544</math> to not have any. | ||
+ | |||
+ | Our probability is thus <math>\dfrac{544}{1024},</math> which simplifies to <math>\dfrac{17}{32},</math> for our answer of <math>17 + 32 = \boxed{049}.</math> | ||
+ | |||
+ | Solution by Ilikeapos | ||
== See also == | == See also == |
Latest revision as of 00:33, 16 May 2024
Problem
In a five-team tournament, each team plays one game with every other team. Each team has a chance of winning any game it plays. (There are no ties.) Let
be the probability that the tournament will produce neither an undefeated team nor a winless team, where
and
are relatively prime integers. Find
.
Solutions
Solution 1
We can use complementary counting: finding the probability that at least one team wins all games or at least one team loses all games.
No more than 1 team can win or lose all games, so at most one team can win all games and at most one team can lose all games.
Now we use PIE:
The probability that one team wins all games is .
Similarity, the probability that one team loses all games is .
The probability that one team wins all games and another team loses all games is .
Since this is the opposite of the probability we want, we subtract that from 1 to get .
Solution 2
There are games in total, and every game can either end in a win or a loss. Therefore, there are
possible outcomes.
Now, computing this probability directly seems a little hard, so let's compute the complement -- the probability that there is an undefeated team, a winless team, or both.
The number of ways that we can have an undefeated team is as there are five ways to choose the team itself and
outcomes for the games that are not concerning the undefeated team. Reversing all the wins to losses yields a winless team, so this situation is symmetrical to the first one. Therefore, there are
ways for an undefeated or winless team.
In the process, however, we have accidentally overcounted the scenario of both an undefeated and winless team. There are ways for this scenario to happen, because there are five ways to choose the undefeated team, four ways for the winless, and three games that don't concern either of the teams. Therefore, there are
ways to have an undefeated and/or winless team, so there are
to not have any.
Our probability is thus which simplifies to
for our answer of
Solution by Ilikeapos
See also
1996 AIME (Problems • Answer Key • Resources) | ||
Preceded by Problem 5 |
Followed by Problem 7 | |
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.