Maths Olympiad Prep

Library / /399 of 740

, 2014

Algebra Difficulty 5.0 AIME, harder Prove it United States

Problem:
Find the smallest positive integer nn such that, if there are initially n+1n+1 townspeople and nn goons, then the probability the townspeople win is less than 1%1\%.

Solution

Solution:
Answer: 66

By a similar inductive argument, the probability for a given nn is
pn=n!(2n+1)!!. p_{n} = \frac{n!}{(2n+1)!!}.
Clearly this is decreasing in nn. It is easy to see that
p5=12345357911=8693>0.01 p_{5} = \frac{1 \cdot 2 \cdot 3 \cdot 4 \cdot 5}{3 \cdot 5 \cdot 7 \cdot 9 \cdot 11} = \frac{8}{693} > 0.01
and
p6=613p5=4869313<0.01 p_{6} = \frac{6}{13} p_{5} = \frac{48}{693 \cdot 13} < 0.01
Hence the answer is n=6n=6. Heuristically, pn+112pnp_{n+1} \approx \frac{1}{2} p_{n} for each nn, so arriving at these estimates for the correct answer of nn is not difficult.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.