HMMT February, 2015

Algebra Difficulty 5.5 AIME, harder Prove it United States

Problem:

Starting with the number $0$ , Casey performs an infinite sequence of moves as follows: he chooses a number from $\{1, 2\}$ at random (each with probability $\frac{1}{2}$ ) and adds it to the current number. Let $p_{m}$ be the probability that Casey ever reaches the number $m$ . Find $p_{20} - p_{15}$ .

Solution

Solution:

We note that the only way $n$ does not appear in the sequence is if $n-1$ and then $n+1$ appears. Hence, we have $p_{0} = 1$ , and $p_{n} = 1 - \frac{1}{2} p_{n-1}$ for $n > 0$ . This gives $p_{n} - \frac{2}{3} = -\frac{1}{2} (p_{n-1} - \frac{2}{3})$ , so that
$p_{n} = \frac{2}{3} + \frac{1}{3} \cdot \left(-\frac{1}{2}\right)^{n}$
so $p_{20} - p_{15}$ is just
$\frac{1 - (-2)^{5}}{3 \cdot 2^{20}} = \frac{11}{2^{20}}$

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

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