Problem:
Lily pads 1,2,3,… lie in a row on a pond. A frog makes a sequence of jumps starting on pad 1. From any pad k the frog jumps to either pad k+1 or pad k+2 chosen randomly and independently with probability 21. The probability that the frog visits pad 7 is qp, where p and q are relatively prime positive integers. Find p+q.
Solution:
Let P(n) be the probability that the frog visits pad n at any time. We initialize with P(1)=1 and define the recurrence:
P(n)=21P(n−1)+21P(n−2) for n≥2.
Compute step-by-step:
P(2)=21⋅1=21
P(3)=21⋅21+21⋅1=41+21=43
P(4)=21⋅43+21⋅21=83+41=85
P(5)=21⋅85+21⋅43=165+166=1611
P(6)=21⋅1611+21⋅85=3211+3210=3221
P(7)=21⋅3221+21⋅1611=6421+6422=6443
Thus, the answer is p+q=43+64=107.
The problems on this page are the property of the MAA's American Mathematics Competitions