LatticeMethod AIME Intermediate
2018


Problem - 4114

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$.


Answer     351

This problem can also be solved using the Lattice Method. From any point, the frog can either go clock-wise or anti-clock-wise. In the grid below, we model clock-wise move by going up and anti-clock-wise move by going right. Because the frog will stop move upon reaching $E$, therefore we only need to count the steps ending at either $P_3$ or $P_4$ within $11$ steps.

The yellow grids above shows the frog reaches either $P_3$ or $P_4$. Accordingly, the top-left and bottom-right corners are beyond the reach. Meanwhile, these grids without numbers on the top-right are those routes which cannot reach either of these two points within $11$ steps. All the numbers are computed using the regular lattice method way. Therefore the final answer is the sum of all the numbers in the $10$ yellow grids, i.e. $$1+3+9+28 + 89+1 + 4+14+47+155 = \boxed{351}$$

report an error