AIME 1996 · 第 6 题

AIME 1996 — Problem 6

专题: Contest Math
难度: L4
来源: AIME

题目详情

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