HMMT 十一月 2012 · THM 赛 · 第 10 题
HMMT November 2012 — THM Round — Problem 10
题目详情
- [ 8 ] In a game of rock-paper-scissors with n people, the following rules are used to determine a champion: (a) In a round, each person who has not been eliminated randomly chooses one of rock, paper, or scissors to play. (b) If at least one person plays rock, at least one person plays paper, and at least one person plays scissors, then the round is declared a tie and no one is eliminated. If everyone makes the same move, then the round is also declared a tie. (c) If exactly two moves are represented, then everyone who made the losing move is eliminated from playing 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 the champion and the game ends. If a game begins with 4 people, what is the expected value of the number of rounds required for a champion to be determined? HMMT November 2012 Saturday 10 November 2012 Theme Round Name Team ID# School Team
解析
- [ 8 ] In a game of rock-paper-scissors with n people, the following rules are used to determine a champion: (a) In a round, each person who has not been eliminated randomly chooses one of rock, paper, or scissors to play. (b) If at least one person plays rock, at least one person plays paper, and at least one person plays scissors, then the round is declared a tie and no one is eliminated. If everyone makes the same move, then the round is also declared a tie. (c) If exactly two moves are represented, then everyone who made the losing move is eliminated from playing 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 the champion and the game ends. If a game begins with 4 people, what is the expected value of the number of rounds required for a champion to be determined? 45 Answer: For each positive integer n , let E denote the expected number of rounds required to n 14 1 determine a winner among n people. Clearly, E = 0. When n = 2, on the first move, there is a 1 3 2 probability that there is a tie, and a probability that a winner is determined. In the first case, the 3 expected number of additional rounds needed is exactly E ; in the second, it is E . Therefore, we get 2 1 the relation 1 2 E = ( E + 1) + ( E + 1) , 2 2 1 3 3 3 from which it follows that E = . 2 2 1 Next, if n = 3, with probability there is only one distinct play among the three players, and with 9 6 2 probability = all three players make different plays. In both of these cases, no players are 27 9 2 eliminated. In all remaining situations, which occur with total probability , two players make one 3 1 play and the third makes a distinct play; with probability two players are eliminated and with 3 1 probability one player is eliminated. This gives the relation 3 1 1 1 E = ( E + 1) + ( E + 1) + ( E + 1) , 3 3 2 1 3 3 3 9 from which we find that E = . 3 4 1 Finally, suppose n = 4. With probability , all four players make the same play, and with probability 27 3 · 6 · 2 4 = , 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 45 so it follows that E = . 4 14 Theme Round