Question

在一个有五支球队的循环赛中，每支球队都与其他每支球队比赛一场。每支球队在其参加的每场比赛中都有 $50\%$ 的获胜概率，且没有平局。设比赛既不产生全胜球队，也不产生全败球队的概率为 $\frac{m}{n}$ ，其中 $m$ 和 $n$ 是互质的正整数。求 $m+n$ 。

In a five-team tournament, each team plays one game with every other team. Each team has a $50\%$ chance of winning any game it plays. There are no ties. Let $\frac{m}{n}$ be the probability that the tournament will produce neither an undefeated team nor a winless team, where $m$ and $n$ are relatively prime positive integers. Find $m+n.$

答案

答案：49

知识点：补集计数容斥原理图论

难度评级：2170

小提示：

比赛结果共有 $2^{\binom52}$ 种等可能情形

There are $2^{\binom52}$ equally likely tournament outcomes

大提示：

对“存在全胜球队”和“存在全败球队”这两个事件使用容斥原理

Use inclusion-exclusion on the events that an undefeated or a winless team exists

解答：

比赛结果共有 $2^{10}=1024$ 种。指定一支全胜球队会确定它的四场比赛，而其余六场可任意决定，所以存在全胜球队的结果有 $5\cdot2^6=320$ 种。存在全败球队的结果也有同样多。若指定的两支不同球队分别全胜和全败，则有七场比赛被确定，其他三支球队之间的三场比赛可任意决定。因此交集中的结果有 $5\cdot4\cdot2^3=160$ 种。由容斥原理，所求结果数为 $1024-320-320+160=544\text{。}$ 概率为 $\frac{544}{1024}=\frac{17}{32}$ ，所以 $m+n=49$ 。

There are $2^{10}=1024$ outcomes. A specified undefeated team forces its four games and leaves the other six arbitrary, so there are $5\cdot2^6=320$ outcomes with an undefeated team. The same count holds for a winless team. If distinct specified teams are undefeated and winless, seven games are forced and the three games among the other teams are arbitrary. Thus the intersection count is $5\cdot4\cdot2^3=160.$ By inclusion-exclusion, the desired count is $1024-320-320+160=544.$ The probability is $\frac{544}{1024}=\frac{17}{32},$ so $m+n=49.$

1996 AIME 第 6 题

答案：49

难度评级：2170

小提示：

大提示：

解答：

其他年份的第 6 题