返回题库

HMMT 十一月 2017 · GEN 赛 · 第 10 题

HMMT November 2017 — GEN Round — Problem 10

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  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
解析

英文解析

  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