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

HMMT November 2014 — THM Round — Problem 2

Find the smallest positive integer n such that, if there are initially 2 n townspeople and 1 goon, then the probability the townspeople win is greater than 50%.

解析

Find the smallest positive integer n such that, if there are initially 2 n townspeople and 1 goon, then the probability the townspeople win is greater than 50%. Answer: 3 We instead consider the probability the goon wins. The game clearly must last n days. The probability the goon is not sent to jail on any of these n days is then 2 n 2 n − 2 2 · · · · · · . 2 n + 1 2 n − 1 3 4 2 8 1 6 8 16 1 If n = 2 then the probability the goon wins is · = > , but when n = 3 we have · = < , 5 3 15 2 7 15 35 2 so the answer is n = 3. Alternatively, the let p be the probability that 2 n townspeople triumph against 1 goon. There is a n 1 chance that the goon is jailed during the first morning and the townspeople win. Otherwise, the 2 n +1 goon eliminates one townperson during the night. We thus have 2 n − 2 townspeople and 1 goon left, so the probability that the town wins is p . We obtain the recursion n − 1 1 2 n p = + p . n n − 1 2 n + 1 2 n + 1 1 7 1 By the previous question, we have the initial condition p = . We find that p = < and 1 2 3 15 2 19 1 p = > , yielding n = 3 as above. 3 35 2