+0

# Help! A tricky question! :)

+1
51
3
+337

Let \(SP_1P_2P_3EP_4P_5 \)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\).

Apr 2, 2020

#1
+420
0

Here you go!

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

This is easily solved by recursion/dynamic programming. To simplify the problem somewhat, let us imagine the seven vertices on a line . We can count the number of left/right (L/R) paths of length  that start at  and end at either  or .

We can visualize the paths using the common grid counting method by starting at the origin , so that a right (R) move corresponds to moving 1 in the positive  direction, and a left (L) move corresponds to moving 1 in the positive  direction. Because we don't want to move more than 2 units left or more than 3 units right, our path must not cross the lines  or . Letting  be the number of such paths from  to  under these constraints, we have the following base cases:

and recursive step  for .

The filled in grid will look something like this, where the lower-left  corresponds to the origin:

The bolded numbers on the top diagonal represent the number of paths from  to  in 2, 4, 6, 8, 10 moves, and the numbers on the bottom diagonal represent the number of paths from  to  in 3, 5, 7, 9, 11 moves. We don't care about the blank entries or entries above the line . The total number of ways is 351.

That is where i found the answer!

Apr 2, 2020
#2
+337
+1

Ok..... so did you just copy and past it? Because there is some latex missing...

Apr 2, 2020
#3
+420
0

Yeah! Click the link to see where i found the answer it is just this link: https://artofproblemsolving.com/wiki/index.php/2018_AIME_I_Problems/Problem_14#Problem

Apr 2, 2020