AIME 1999 · 第 13 题

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. Further, note that these are all the valid combinations, as the team with 1 win must beat the team with 0 wins, the team with 2 wins must beat the teams with 1 and 0 wins, and so on; thus, this uniquely defines a combination.

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 \rfloor + \left \lfloor \frac{40}{16} \right \rfloor + \left \lfloor \frac{40}{32} \right \rfloor = 20 + 10 + 5 + 2 + 1 = 38.$

$780-38 = \boxed{742}$.