2006 AIME II Problem 10

Question

Seven teams play a soccer tournament in which each team plays every other team exactly once. No ties occur, each team has a

50\%

chance of winning each game it plays, and the outcomes of the games are independent. In each game, the winner is awarded

1

point and the loser gets

0

points. The total points are accumulated to decide the ranks of the teams. In the first game of the tournament, team

A

beats team

B.

The probability that team

A

finishes with more points than team

B

is

\frac{m}{n},

where

m

and

n

are relatively prime positive integers. Find

m + n.

Answer

Answer: 831

Concepts:binomial probability symmetry combinations

Difficulty rating: 2650

Small hint:

A

starts one point ahead and never plays

B

again, so

A

finishes ahead exactly when

A

wins at least as many of its

5

remaining games as

B

does.

Big hint:

The chance the remaining win counts are equal is

\sum_k \frac{\binom{5}{k}^2}{2^{10}};

by symmetry the other outcomes split evenly between the teams.

Solution:

Teams

A

and

B

each have

5

games left, none against each other, so all

2^5 \cdot 2^5 = 1024

outcomes are equally likely. Since

A

already leads by one point,

A

finishes with more points exactly when

A

wins at least as many remaining games as

B

does.

The number of outcomes with equal win counts is

\sum_{k=0}^{5} \binom{5}{k}^2 = \binom{10}{5} = 252.

By symmetry, the other

1024 - 252 = 772

outcomes split evenly between

A

winning more and

B

winning more.

So the probability is

\frac{252 + 386}{1024} = \frac{638}{1024} = \frac{319}{512},

and

m + n = 319 + 512 = 831.