Question

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 $\frac{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 positive integers. Find $m+n.$

Answer

Answer: 49

Concepts:complementary counting inclusion-exclusion graph theory

Difficulty rating: 2170

Small Hint:

There are $2^{\binom52}$ equally likely tournament outcomes

Big Hint:

Use inclusion-exclusion on the events that an undefeated or a winless team exists

Solution:

There are $2^{10}=1024$ outcomes. A specified undefeated team forces its four games and leaves the other six arbitrary, so there are $5\cdot2^6=320$ outcomes with an undefeated team. The same count holds for a winless team. If distinct specified teams are undefeated and winless, seven games are forced and the three games among the other teams are arbitrary. Thus the intersection count is $5\cdot4\cdot2^3=160.$ By inclusion-exclusion, the desired count is $1024-320-320+160=544.$ The probability is $\frac{544}{1024}=\frac{17}{32},$ so $m+n=49.$

1996 AIME Problem 6

Answer: 49

Difficulty rating: 2170

Small Hint:

Big Hint:

Solution:

Problem 6 in Other Years