10
$\begingroup$

Five teams play a tournament in which every team plays every other team exactly once. No ties occur, and each team has a $1/2$ probability of winning any game it plays. Find the probability that no team wins/loses all the games.

My try:

Each team plays all other teams once. So there are $\binom{5}{2} = 10$ games. For each game there are 2 possible outcomes so there's a total of $2^{10}$ possible outcomes.

Number of outcomes where $1$ team wins all its games: Let's say team A wins all its games ($4$ in total). Then other $6$ games can end in $2$ possible outcomes. Since anyone team could win all its games, we get $5 \times 2^6 $ as the number of outcomes where $1$ team wins all its games.

Similarly by symmetry, we get $5 \times 2^6 $ as the number of outcomes where $1$ team loses all its games.

It's also possible for $1$ team to win all its games, and another team to lose all its games. But these will have been included in both totals above (i.e. calculated twice), so we must subtract this amount once from the totals above: Let's say team A wins all its games and team B loses all it's games (these include $7$ games, $4$ games for team A and $4$ games for team B, but we must remember that teams A and B play each other once, so there are only $7$ games in which team A or team B plays with certain victory or losing respectively). So, since any of the $5$ teams could be the one to win all its games, and any of the $4$ remaining teams could be the one to lose all its games, we get $5 \times 4 \times 2^3 = 20 \times 2^3. $

Probability that at least one team wins/loses all their games is $\frac{(5 \times 2^6 + 5 \times 2^6 − 20 \times 2^3)}{ 2^{10}} = \frac{15}{32}. $ Hence, probability that no team wins/loses all their games is $\frac{17}{32}.$

Is this alright?

$\endgroup$
  • 2
    $\begingroup$ Yes.${}{}{}{}$ $\endgroup$ – Parcly Taxel Sep 15 '17 at 4:57
  • $\begingroup$ @ParclyTaxel Thanks for the confirmation. I was getting confused between using $5P2$ and $5C2$ in the case where one team wins and the other team loses all it's games. Can you tell me when do we use $5C2$? $\endgroup$ – Random-generator Sep 15 '17 at 5:05
  • 2
    $\begingroup$ We'd use 5C2 when there would be nothing distinguishing the two selected teams, such as if both had four wins; here though one has five wins and the other five losses, so 5P2 is called for. $\endgroup$ – Parcly Taxel Sep 15 '17 at 5:07
5
$\begingroup$

Yes, you are right.

Moreover, the similar method can be used to solve a more general problem:

$N$ teams play a tournament in which every team plays every other team exactly once. No ties occur, and each team has a $\frac{1}{2}$ probability of winning any game it plays. Find the probability that no team wins/loses all the games.

Any team has the probability of $\frac{1}{2^{N - 1}}$ to win all games, or (symmetrically) to lose all games. Because there are $N$ teams and only one of them at a time can be the complete winner (or loser), then the probability that one team wins (or loses) all the games is $\frac{N}{2^{N - 1}} \cdot 2$. Now, the probability, that there are the complete winner and the complete loser at the same time is $\frac{N(N-1)}{2^{2N - 3}}$ (which we find by applying the same method to the pairs of teams). Thus by inclusion-exclusion principle, the final probability is $1 - \frac{N}{2^{N-2}} + \frac{N(N - 1)}{2^{2N - 3}}$, which, indeed, does collapse into $\frac{17}{32}$ when $N = 5$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.