1996 AIME 第 6 题

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 题