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 round robin tournament, such that each pair of people play exactly once, and there are no ties. In each of the ten games, the two players both have a 50% chance of winning, and the results of the games are independent. Compute the probability that there exist four distinct players P , P , P , P such that P 1 2 3 4 i beats 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 round robin tournament, such that each pair of people play exactly once, and there are no ties. In each of the ten games, the two players both have a 50% chance of winning, and the results of the games are independent. Compute the probability that there exist four distinct players P , P , P , P such that P 1 2 3 4 i beats P for i = 1 , 2 , 3 , 4. (We denote P = P ). i +1 5 1 Proposed by: Steven Hao 49 Answer: 64 We make the following claim: if there is a 5-cycle (a directed cycle involving 5 players) in the tourna- 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 C then A, C, D, E forms a 4-cycle, and similar if B beats D , C beats E , and so on. However, if all five reversed 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. ( ) 5 Case 1: There is a 3-cycle. Assume that A beats B , B beats C , and C beats A . (There are = 10 3 ways to choose the cycle and 2 ways to orient the cycle.) Then D either beats all three or is beaten by 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 remaining person 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 loses to 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 − = . 10 2 64 64 64