HMMT-Nov 2014 thm, Problem 4

Suppose there are initially 1001 townspeople and two goons. What is the probability that, when the game ends, there are exactly 1000 people in jail?

Solution: By considering the parity of the number of people in jail, we see that this situation arises if and only if the goons win after the 500th night. That means that at this point we must have exactly one townsperson and two goons remaining. In other words, this situation arises if and only if no goon is ever sent to jail. The probability that this occurs is \[ \frac{1001}{1003} \cdot \frac{999}{1001} \cdot \frac{997}{999} \cdot \ldots \frac{3}{5}=\frac{3}{1003} \] $\fbox{\frac{3}{1003}}$.

Answer: \frac{3}{1003}