Question

四十支队伍进行一场锦标赛，每支队伍都与其他每支队伍恰好比赛一次。没有平局，每支队伍在任意一场比赛中获胜的概率都是 $50\%$ 。没有两支队伍获胜场数相同的概率为 $\frac{m}{n}$ ，其中 $m$ 和 $n$ 是互质的正整数。求 $\log_2 n$ 。

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.$

答案

答案：742

知识点：基本概率排列勒让德公式

难度评级：2650

解答：

共有 $\binom{40}{2} = 780$ 场比赛，因此有 $2^{780}$ 个等可能结果。如果全部 $40$ 个胜场数都不同，它们必须正好是 $0, 1, \ldots, 39$ 。此时胜 $39$ 场的队伍击败所有队伍，胜 $38$ 场的队伍只输给那支队伍，依此类推：把这些胜场数分配给各队后，每场比赛结果都被确定。反过来，每个 $40!$ 种分配都对应唯一一种比赛结果，所以概率为 $\frac{40!}{2^{780}}$ 。

由勒让德公式， $40!$ 中因子 $2$ 的指数为 $20 + 10 + 5 + 2 + 1 = 38$ 。约成最简分数后，分母为 $n = 2^{780 - 38} = 2^{742}$ ，所以 $\log_2 n = 742$ 。

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 第 13 题

答案：742

难度评级：2650

解答：

其他年份的第 13 题