Problem:
Let SP1P2P3EP4P5 be a heptagon. A frog starts jumping at vertex S. From any vertex of the heptagon except E, the frog may jump to either of the two adjacent vertices. When it reaches vertex E, the frog stops and stays there. Find the number of distinct sequences of jumps of no more than 12 jumps that end at E.
Solution:
Define A={S,P1},B={P2,P5}, and C={P3,P4}. Then the frog can reach vertex E on jump n only if it reaches a vertex in C on jump n−1. The frog can reach a vertex in C on jump n only if it reaches a vertex in B on jump n−1. The frog can reach a vertex in B on jump n only if it reaches a vertex in either A or C on jump n−1. Finally, the frog can reach a vertex in A on jump n only if it reaches a vertex in either A or B on jump n−1. Let an,bn, and cn be the number of paths of length n that end in set A,B, and C, respectively. Then an+1=an+bn,bn+1=an+cn, and cn+1=bn. Replacing the b terms with c terms yields an+1=an+cn+1 and cn+2=an+cn, which implies that an=cn+2−cn. Finally, this gives cn+3−cn+1=cn+2−cn+cn+1, which implies that cn+3=cn+2+2cn+1−cn. It is easy to see that c0=0,c1=0, and c2=1. From the recursive formula, it is easy to complete the following table.
ncn00102131435469714828947108911155
The frog can end at E on jump n if it enters C on the jump n−1. Thus the number of paths of no more than 12 jumps that end at E is 0+0+1+1+3+ 4+9+14+28+47+89+155=351.
The problems on this page are the property of the MAA's American Mathematics Competitions