Problem:
Flora the frog starts at 0 on the number line and makes a sequence of jumps to the right. In any one jump, independent of previous jumps, Flora leaps a positive integer distance m with probability 1/2m. What is the probability that Flora will eventually land at 10?
Answer Choices:
A. 5125​
B. 102445​
C. 1024127​
D. 1024511​
E. 21​
Solution:
Suppose integers a1​,a2​,a3​,…,ak​ satisfy 0<a1​<a2​<a3​<⋯<ak​<10. Then Flora lands on the sequence of numbers a1​,a2​,a3​,…,ak​,10 with probability
2a1​1​⋅2a2​−a1​1​⋅2a3​−a2​1​⋯210−ak​1​=2101​
Therefore every route Flora takes to get to 10 has the same probability. There is one such route for every subset of {1,2,3,…,9}, so there are 29 routes. It follows that the requested probability is
21029​=21​
Note: In fact, the probability Flora will eventually land on any specific positive integer distance from 0 is 21​.
This may be proved by induction. For every positive integer n, let pn​ be the probability that Flora eventually lands on n, starting from 0 . Then p1​=21​, because either she lands on 1 with probability 21​ on her very first jump, or she jumps over 1 and never returns to it. (This is the base case of the induction argument.) And, for any integer k≥1, if p1​=p2​=p3​=⋯=pk​=21​, then
pk+1​​=2k+11​+p1​⋅2k1​+p2​⋅2k−11​+⋯+pk​⋅21​=2k+11​+21​(2k1​+2k−11​+⋯+21​)=2k+11​+21​(1−2k1​)=(E)21​​​
The problems on this page are the property of the MAA's American Mathematics Competitions