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
2a11⋅2a2−a11⋅2a3−a21⋯210−ak1=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