2018 AIME I Problems/Problem 14

Let be a heptagon. A frog starts jumping at vertex . From any vertex of the heptagon except , the frog may jump to either of the two adjacent vertices. When it reaches vertex , the frog stops and stays there. Find the number of distinct sequences of jumps of no more than jumps that end at .

Solution

(incomplete, someone help format this) Make a table showing how many ways there are to get to each vertex in a certain amount of jumps. all equal the sum of their adjacent elements in the previous jump. equals the previous . equals the previous . Each equals the previous adjacent element in the previous jump.

Jump & E & P_3 & P_2 & P_1 & S & P_5 & P_4 & E

0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 2 0 0 1 0 2 0 1 0 3 0 1 0 3 0 3 0 1 4 1 0 4 0 6 0 3 1 5 1 4 0 10 0 9 0 4 6 5 0 14 0 19 0 9 4 7 5 14 0 33 0 28 0 13 8 19 0 47 0 61 0 28 13 9 19 47 0 108 0 89 0 41 10 66 0 155 0 197 0 89 41 11 66 155 0 352 0 286 0 130 12 221 - - - - - - 130

The number of ways to jump to the ends within 12 jumps is .