AMC12 2016 12A, Problem 19

Jerry starts at $0$ on the real number line. He tosses a fair coin $8$ times. When he gets heads, he moves $1$ unit in the positive direction; when he gets tails, he moves $1$ unit in the negative direction. The probability that he reaches $4$ at some time during this process $\frac{a}{b},$ where $a$ and $b$ are relatively prime positive integers. What is $a + b?$ (For example, he succeeds if his sequence of tosses is $HTHHHHHH.$)

Solution: For $6$ to $8$ heads, we are guaranteed to hit $4$ heads, so the sum here is $\binom{8}{2}+\binom{8}{1}+\binom{8}{0}=28+8+1=37$. For $4$ heads, you have to hit the $4$ heads at the start so there's only one way, $1$. For $5$ heads, we either start off with $4$ heads, which gives us $_4\text{C}_1=4$ ways to arrange the other flips, or we start off with five heads and one tail, which has $6$ ways minus the $2$ overlapping cases, $\text{HHHHHTTT}$ and $\text{HHHHTHTT}$. Total ways: $8$. Then we sum to get $46$. There are a total of $2^8=256$ possible sequences of $8$ coin flips, so the probability is $\frac{46}{256}=\frac{23}{128}$. Summing, we get $23+128=\fbox{151}$.

Answer: 151