1999 AIME Problems/Problem 13

Problem

Forty teams play a tournament in which every team plays every other team exactly once. No ties occur, and each team has a $\displaystyle 50 \%$ chance of winning any game it plays. The probability that no two teams win the same number of games is $\displaystyle m/n,$ where $\displaystyle m_{}$ and $\displaystyle n_{}$ are relatively prime positive integers. Find $\displaystyle \log_2 n.$

Solution

Now one team must win 0 games, one team must win one game, ... , and one team must win all 39 games it plays. Now let's assume that team one wins all games, ... , and team 40 loses all games. The probability that team 40 wins all games is $\dfrac{1}{2^{39}}$ . Now that team 39 has lost it's game, it has a probability of $\dfrac{1}{2^{38}}$ of winning all of the other games. So on, until we get

$\dfrac{1}{2^{39+38+\cdots+1}$ (Error compiling LaTeX. Unknown error_msg)

But that was assuming that we knew which team got what score. Now we need to account of the permutations of each team:

$\dfrac{40!}{2^{780}}$

Now we need to find how many 2's there are in 40. There are

$\lfloor \dfrac{40}{2} \rfloor +\lfloor \dfrac{40}{4} \rfloor +\lfloor \dfrac{40}{8} \rfloor +\lfloor \dfrac{40}{16} \rfloor +\lfloor \dfrac{40}{32} \rfloor = 38$

Therefore,

$n=2^{780-38}=2^{742}$

and

$\log_{2} n =\boxed{742}$

1999 AIME (Problems • Answer Key • Resources)
Preceded by Problem 12	Followed by Problem 14
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

Page

Toolbox

Search

1999 AIME Problems/Problem 13

Problem

Solution

See also