HMMT 十一月 2012 · THM 赛 · 第 10 题

英文解析

10. [ 8 ] In a game of rock-paper-scissors with n people, the following rules are used to determine achampion:
    (a) In a round, each person who has not been eliminated randomly chooses one of rock, paper, orscissors to play.
    (b) If at least one person plays rock, at least one person plays paper, and at least one person playsscissors, then the round is declared a tie and no one is eliminated. If everyone makes the samemove, then the round is also declared a tie.
    (c) If exactly two moves are represented, then everyone who made the losing move is eliminated fromplaying in all further rounds (for example, in a game with 8 people, if 5 people play rock and 3
    people play scissors, then the 3 who played scissors are eliminated).
    (d) The rounds continue until only one person has not been eliminated. That person is declared thechampion and the game ends.
    If a game begins with 4 people, what is the expected value of the number of rounds required for achampion to be determined?
    Answer: For each positive integer n , let E denote the expected number of rounds required to 45
    14 ndetermine a winner among n people. Clearly, E = 0. When n = 2, on the first move, there is a 1
    probability that there is a tie, and a probability that a winner is determined. In the first case, the 231
    expected number of additional rounds needed is exactly E ; in the second, it is E . Therefore, we get 3
    2 1
    the relation
    1 2
    E = ( E + 1) + ( E + 1) ,
    2 2 1
    3 3
    from which it follows that E = .3
    Next, if n = 3, with probability there is only one distinct play among the three players, and with 122
    6 29
    probability = all three players make different plays. In both of these cases, no players are
    27 9
    eliminated. In all remaining situations, which occur with total probability , two players make one 2
    play and the third makes a distinct play; with probability two players are eliminated and with 13
    probability one player is eliminated. This gives the relation 13
    1 1 13
    E = ( E + 1) + ( E + 1) + ( E + 1) ,
    3 3 2 1
    3 3 3
    from which we find that E = .9
    Finally, suppose n = 4. With probability , all four players make the same play, and with probability 143
    3 · 6 · 2 427 = , two players make one play, and the other two players make the other two plays; in both cases
    81 9
    1 4 13
    no players are eliminated, with total probability + = over the two cases. With probability
    27 9 27
    6 · 4 8 = , three players make one play and the fourth makes another; thus, there is a probability of
    81 27
    4 4
    for exactly one player being eliminated and a probability of of three players being eliminated.
    27 27
    Theme Round
    6 · 3 2
    Then, there is a remaining probability of = , two players make one play and the other two players
    81 9
    make another. Similar analysis from before yields
    13 4 2 4
    E = ( E + 1) + ( E + 1) + ( E + 1) + ( E + 1) ,
    4 4 3 2 1
    27 27 9 27
    so it follows that E = .45
    Theme Round 144