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 squarelyfacing 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 pairoff going clockwise, starting from the chosen one. Each pair faces off in Pushover, and the losers leavethe circle. What is the probability that players 1 and 2 face each other in the last round? Expressnyour answer in terms of n .
解析
英文解析
- Let n be a positive integer, and let Pushover be a game played by two players, standingsquarely facing each other, pushing each other, where the first person to lose balancen +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, thereferee randomly chooses one of the surviving players, and the players pair off goingclockwise, starting from the chosen one. Each pair faces off in Pushover, and the losersnleave the circle. What is the probability that players 1 and 2 face each other in thelast round? Express your answer in terms of n .
n 2
2 − 1
Answer:
8 n
Solution: At any point during this competition, we shall say that the situation isnliving if both players 1 and 2 are still in the running. A living situation is far ifthose two players are diametrically opposite each other, and near otherwise, in whichcase (as one can check inductively) they must be just one person shy of that maximalseparation. At the start of the tournament, the situation is living and near. In eachof rounds 1 to n , a far situation can never become near, and a near situation can staynear 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 withk k kprobability 1 / 8 , and far with probability 1 / 4 − 1 / 8 . In round n , a far situation hasa 1 / 4 probability of staying living, whereas a near situation has only a 1 / 8 probabilityof staying living. But if the situation is living at the beginning of the last round, itcan only be far, so we can say with complete generality that, at the end of round k ,
k kwhere 1 ≤ k ≤ n , the situation is living and far with probability 1 / 4 − 1 / 8 . We areinterested in finding the probability that the situation is living at the end of round nn
1 1 2 − 1
(and hence far); that probability is thus − = .
n n n
4 8 8