Question

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

Answer

Answer: 742

Concepts:basic probability permutations Legendre’s Formula

Difficulty rating: 2650

Solution:

There are $\binom{40}{2} = 780$ games, hence $2^{780}$ equally likely outcomes. If all $40$ win totals are distinct, they must be exactly $0, 1, \ldots, 39.$ In that case the team with $39$ wins beat everyone, the team with $38$ wins beat everyone except that team, and so on: the assignment of totals to teams determines every game. Conversely each of the $40!$ assignments arises from exactly one outcome, so the probability is $\frac{40!}{2^{780}}.$

By Legendre's formula the power of $2$ dividing $40!$ is $20 + 10 + 5 + 2 + 1 = 38.$ In lowest terms the denominator is therefore $n = 2^{780 - 38} = 2^{742},$ so $\log_2 n = 742.$

1999 AIME Problem 13

Answer: 742

Difficulty rating: 2650

Solution:

Problem 13 in Other Years