1999 AIME Problems/Problem 13

From AoPSWiki

Problem

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 mn,$ where $m_{}$ and $n_{}$ are relatively prime positive integers. Find $\log_2 n.$

Solution

There are ${40 \choose 2} = 780$ total pairings of teams, and thus $2^{780}$ possible outcomes. In order for no two teams to win the same number of games, they must each win a different number of games. Since the minimum and maximum possible number of games won are 0 and 39 respectively, and there are 40 teams in total, each team corresponds uniquely with some $k$ , with $0 \leq k \leq 39$ , where $k$ represents the number of games the team won. With this in mind, we see that there are a total of $40!$ outcomes in which no two teams win the same number of games.

The desired probability is thus $\frac{40!}{2^{780}}$ . We wish to simplify this into the form $\frac{m}{n}$ , where $m$ and $n$ are relatively prime. The only necessary step is to factor out all the powers of 2 from $40!$ ; the remaining number is clearly relatively prime to all powers of 2.

The number of powers of 2 in $40!$ is $\left \lfloor \frac{40}{2} \right \rfloor + \left \lfloor \frac{40}{4} \right \rfloor + \left \lfloor \frac{40}{8} \right \rf...$

Letting $y = \frac{40!}{2^{38}}$ , we have that $\frac{40!}{2^{780}} = \frac{2^{38} y}{2^{780}} = \frac{y}{2^{742}}$ . Since $y$ and $2^{742}$ are relatively prime, our quotient is in the desired form. Our answer is thus $\log_2 2^{742} = \boxed{742}$ .

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

Personal tools

Navigation

Search

Toolbox

1999 AIME Problems/Problem 13

From AoPSWiki

Problem

Solution

See also