Problem:
Freddy the frog is jumping around the coordinate plane searching for a river, which lies on the horizontal line . A fence is located at the horizontal line . On each jump Freddy randomly chooses a direction parallel to one of the coordinate axes and moves one unit in that direction. When he is at a point where , with equal likelihoods he chooses one of three directions where he either jumps parallel to the fence or jumps away from the fence, but he never chooses the direction that would have him cross over the fence to where . Freddy starts his search at the point and will stop once he reaches a point on the river. Find the expected number of jumps it will take Freddy to reach the river.
Solution:
Let be the expected number of jumps it will take Freddy to reach the river when he is a distance from it. The problem asks for the value of . Note that , and for each with there is a probability of that
Freddy will stay the same distance from the river, a probability of that he will get one jump closer to the river, and a probability of that he will get one jump farther away. Thus
which simplifies to . For the special case ,
which simplifies to . Summing the equations for yields
This simplifies to . Combining this with the equation yields . From the recurrence , it follows that and .
The problems on this page are the property of the MAA's American Mathematics Competitions