HMMT 二月 2006 · COMB 赛 · 第 7 题
HMMT February 2006 — COMB Round — Problem 7
题目详情
- Let n be a positive integer, and let Pushover be a game played by two players, standing squarely facing each other, pushing each other, where the first person to lose balance loses. At the HMPT, n +1 n +1 2 competitors, numbered 1 through 2 clockwise, stand in a circle. They are equals in Pushover: whenever two of them face off, each has a 50% probability of victory. The tournament unfolds in n + 1 rounds. In each round, the referee randomly chooses one of the surviving players, and the players pair off going clockwise, starting from the chosen one. Each pair faces off in Pushover, and the losers leave n the circle. What is the probability that players 1 and 2 face each other in the last round? Express your answer in terms of n .
解析
- Let n be a positive integer, and let Pushover be a game played by two players, standing squarely facing each other, pushing each other, where the first person to lose balance n +1 n +1 loses. At the HMPT, 2 competitors, numbered 1 through 2 clockwise, stand in a circle. They are equals in Pushover: whenever two of them face off, each has a 50% probability of victory. The tournament unfolds in n + 1 rounds. In each round, the referee randomly chooses one of the surviving players, and the players pair off going clockwise, starting from the chosen one. Each pair faces off in Pushover, and the losers n leave the circle. What is the probability that players 1 and 2 face each other in the last round? Express your answer in terms of n . 2 n 2 − 1 Answer: n 8 Solution: At any point during this competition, we shall say that the situation is n living if both players 1 and 2 are still in the running. A living situation is far if those two players are diametrically opposite each other, and near otherwise, in which case (as one can check inductively) they must be just one person shy of that maximal separation. At the start of the tournament, the situation is living and near. In each of rounds 1 to n , a far situation can never become near, and a near situation can stay near or become far with equal likelihood. In each of rounds 1 to n − 1, a living situation has a 1 / 4 probability of staying living. Therefore, at the end of round k , where 1 ≤ k ≤ n − 1, the situation is near with k k k probability 1 / 8 , and far with probability 1 / 4 − 1 / 8 . In round n , a far situation has a 1 / 4 probability of staying living, whereas a near situation has only a 1 / 8 probability of staying living. But if the situation is living at the beginning of the last round, it can only be far, so we can say with complete generality that, at the end of round k , k k where 1 ≤ k ≤ n , the situation is living and far with probability 1 / 4 − 1 / 8 . We are interested in finding the probability that the situation is living at the end of round n n 1 1 2 − 1 (and hence far); that probability is thus − = . n n n 4 8 8