HMMT November, 2021

Combinatorics Difficulty 4.6 AIME Find the answer United States

Problem:
A counter begins at $0$ . Then, every second, the counter either increases by $1$ or resets back to $0$ with equal probability. The expected value of the counter after ten seconds can be written as $\frac{m}{n}$ , where $m, n$ are positive integers and $\operatorname{gcd}(m, n)=1$ . Find $100m+n$ .

Your answer

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

Solution

Solution:
The probability that the counter is equal to $k$ corresponds to the last $k$ seconds all being increases by $1$ and the second before that being a reset to $0$ , which happens with probability $2^{-k-1}$ . The only contradiction to this is when $k=10$ and the counter gets there by only counting $1$ 's. Therefore, the expected value is simply the sum of probabilities times the counter, which is
$\frac{10}{2^{10}} + \sum_{k=1}^{9} \frac{k}{2^{k+1}} = \left(\frac{1}{2^{10}} + \sum_{k=1}^{9} \frac{1}{2^{k+1}}\right) + \left(\frac{1}{2^{10}} + \sum_{k=2}^{9} \frac{1}{2^{k+1}}\right) + \ldots + \frac{1}{2^{10}} = \frac{1}{2} + \frac{1}{4} + \ldots + \frac{1}{2^{10}} = \frac{1023}{1024}$

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.