HMMT 十一月 2014 · THM 赛 · 第 5 题

HMMT November 2014 — THM Round — Problem 5

Suppose that there are initially eight townspeople and one goon. One of the eight townspeople is named Jester . If Jester is sent to jail during some morning, then the game ends immediately in his sole victory. (However, the Jester does not win if he is sent to jail during some night.) Find the probability that only the Jester wins. Parabolas A parabola is the set of points in the plane equidistant from a point F (its focus ) and a line ℓ (its directrix). F ℓ 2 Parabolas can be represented as polynomial equations of degree two, such as y = x .

解析

Suppose that there are initially eight townspeople and one goon. One of the eight townspeople is named Jester . If Jester is sent to jail during some morning, then the game ends immediately in his sole victory. (However, the Jester does not win if he is sent to jail during some night.) Find the probability that only the Jester wins. 1 Answer: Let a denote the answer when there are 2 n − 1 regular townies, one Jester, and one n 3 1 goon. It is not hard to see that a = . Moreover, we have a recursion 1 3 ( ) 1 1 2 n − 1 1 2 n − 2 a = · 1 + · 0 + · 0 + · a . n n − 1 2 n + 1 2 n + 1 2 n + 1 2 n − 1 2 n − 1 1 The recursion follows from the following consideration: during the day, there is a chance the Jester 2 n +1 1 is sent to jail and a chance the goon is sent to jail, at which point the game ends. Otherwise, there 2 n +1 1 is a chance that the Jester is selected to be jailed from among the townies during the evening. If 2 n − 1 none of these events occur, then we arrive at the situation of a . n − 1 1 1 Since a = , we find that a = for all values of n . This gives the answer. 1 n 3 3