HMMT 十一月 2017 · GEN 赛 · 第 10 题
HMMT November 2017 — GEN Round — Problem 10
题目详情
英文原题
- Five equally skilled tennis players named Allen, Bob, Catheryn, David, and Evan play in a roundrobin tournament, such that each pair of people play exactly once, and there are no ties. In each ofthe ten games, the two players both have a 50% chance of winning, and the results of the games areindependent. Compute the probability that there exist four distinct players P , P , P , P such that P
1 2 3 4 ibeats P for i = 1 , 2 , 3 , 4. (We denote P = P ).
i +1 5 1
解析
英文解析
- Five equally skilled tennis players named Allen, Bob, Catheryn, David, and Evan play in a roundrobin tournament, such that each pair of people play exactly once, and there are no ties. In each ofthe ten games, the two players both have a 50% chance of winning, and the results of the games areindependent. Compute the probability that there exist four distinct players P , P , P , P such that P
1 2 3 4 ibeats P for i = 1 , 2 , 3 , 4. (We denote P = P ).
i +1 5 1
Proposed by: Steven Hao
Answer:49
We make the following claim: if there is a 5-cycle (a directed cycle involving 5 players) in the tourna-64
ment, then there is a 4-cycle.
Proof: Assume that A beats B , B beats C , C beats D , D beats E and E beats A . If A beats Cthen A, C, D, E forms a 4-cycle, and similar if B beats D , C beats E , and so on. However, if all fivereversed matches occur, then A, D, B, C is a 4-cycle.
Therefore, if there are no 4-cycles, then there can be only 3-cycles or no cycles at all.
( )
Case 1: There is a 3-cycle. Assume that A beats B , B beats C , and C beats A . (There are = 105
ways to choose the cycle and 2 ways to orient the cycle.) Then D either beats all three or is beaten by 3
all three, because otherwise there exists two people X and Y in these three people such that X beats
Y , and D beats Y but is beaten by X , and then X, D, Y, Z will form a 4-cycle ( Z is the remainingperson of the three). The same goes for E . If D and E both beat all three or are beaten by all three,
then there is no restriction on the match between D and E . However, if D beats all three and E losesto all three, then E cannot beat D because otherwise E, D, A, B forms a 4-cycle. This means that
A, B, C is the only 3-cycle in the tournament, and once the cycle is chosen there are 2 · 2 + 2 · 1 = 6
ways to choose the results of remaining matches, for 10 · 2 · 6 = 120 ways in total.
Case 2: There are no cycles. This means that the tournament is a complete ordering (the person with a higher rank always beats the person with a lower rank). There are 5! = 120 ways in this case as well.
120+120 15 15 49
Therefore, the probability of not having a 4-cycle is = , and thus the answer is 1 − = .
2 64 64 6410