Library / /11 of 68

, 2017

Combinatorics Difficulty 4.6 AIME Find the answer United States

Problem:

Emily starts with an empty bucket. Every second, she either adds a stone to the bucket or removes a stone from the bucket, each with probability $\frac{1}{2}$ . If she wants to remove a stone from the bucket and the bucket is currently empty, she merely does nothing for that second (still with probability $\frac{1}{2}$ ). What is the probability that after 2017 seconds her bucket contains exactly 1337 stones?

Your answer

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Solution:

Answer: $\frac{\binom{2017}{340}}{2^{2017}}$

Replace 2017 with $n$ and 1337 with $k$ and denote the general answer by $f(n, k)$ . I claim that $f(n, k) = \frac{\binom{n}{\frac{n-k}{2}}}{2^n}$ .

We proceed by induction on $n$ .

The claim is obviously true for $n=0$ since $f(0,0)=1$ . Moreover, we have that
$f(n, 0) = \frac{1}{2} f(n-1, 0) + \frac{1}{2} f(n-1, 1)$
and
$f(n, k) = \frac{1}{2} f(n-1, k-1) + \frac{1}{2} f(n-1, k+1)$
for $k > 0$ , so the inductive step is immediate by Pascal's identity. This concludes the proof.

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.