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?
Best Answer
Yes, you are right.
Moreover, the similar method can be used to solve a more general problem:
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$.