Difference between revisions of "1996 AIME Problems/Problem 6"
m (→Solution) |
m (→Solution 2) |
||
| (5 intermediate revisions by one other user 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 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 23:33, 15 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. 
