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

英文解析

2. Find the smallest positive integer n such that, if there are initially 2 n townspeople and 1 goon, thenthe 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 anchance that the goon is jailed during the first morning and the townspeople win. Otherwise, the 1
   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 recursionn − 1
   1 2 np = + 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.
   35 23