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 "1996 AIME Problems/Problem 6"

(→‎Solutions)
m (→‎Solution 2)
 
(3 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>.
  
−
= Solutions =
+
== Solutions ==
  
−
== Solution 1 ==  
+
=== 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 24: Line 24:
 
<math>17+32=\boxed{049}</math>
 
<math>17+32=\boxed{049}</math>
  
−
== Solution 2 ==  
+
=== 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.
 
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.
Line 30: Line 30:
 
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.
 
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 wings 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.
+
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.
 
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.

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 $50\%$ chance of winning any game it plays. (There are no ties.) Let $\dfrac{m}{n}$ be the probability that the tournament will produce neither an undefeated team nor a winless team, where $m$ and $n$ are relatively prime integers. Find $m+n$.

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 $5\cdot \left(\frac{1}{2}\right)^4=\frac{5}{16}$.

Similarity, the probability that one team loses all games is $\frac{5}{16}$.

The probability that one team wins all games and another team loses all games is $\left(5\cdot \left(\frac{1}{2}\right)^4\right)\left(4\cdot \left(\frac{1}{2}\right)^3\right)=\frac{5}{32}$.

$\frac{5}{16}+\frac{5}{16}-\frac{5}{32}=\frac{15}{32}$

Since this is the opposite of the probability we want, we subtract that from 1 to get $\frac{17}{32}$.

$17+32=\boxed{049}$

Solution 2

There are $\dbinom{5}{2} = 10$ games in total, and every game can either end in a win or a loss. Therefore, there are $2^{10} = 1024$ 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 $5 \cdot 2^6,$ as there are five ways to choose the team itself and $2^6$ 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 $5 \cdot 2^6 + 5 \cdot 2^6$ 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 $5 \cdot 4 \cdot 2^3$ 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 $5 \cdot 2^6 + 5 \cdot 2^6 - 5 \cdot 4 \cdot 2^3 = 480$ ways to have an undefeated and/or winless team, so there are $1024 - 480 = 544$ to not have any.

Our probability is thus $\dfrac{544}{1024},$ which simplifies to $\dfrac{17}{32},$ for our answer of $17 + 32 = \boxed{049}.$

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1996_AIME_Problems/Problem_6&oldid=219373"