2018 AIME I Problem 14

Attempt Problem 14 of the 2018 AIME I below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2018 AIME I solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

14.

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

Answer: 351
Concepts:recursive countingsymmetry
Difficulty rating: 3160
Solution:

Group the vertices into classes A={S,P1},\mathcal{A} = \{S, P_1\}, B={P2,P5},\mathcal{B} = \{P_2, P_5\}, and C={P3,P4}.\mathcal{C} = \{P_3, P_4\}. Each vertex of A\mathcal{A} adjoins one vertex of A\mathcal{A} and one of B;\mathcal{B}; each vertex of B\mathcal{B} adjoins one of A\mathcal{A} and one of C;\mathcal{C}; and each vertex of C\mathcal{C} adjoins one of B\mathcal{B} and the absorbing vertex E.E. Hence if an,a_n, bn,b_n, cnc_n count the nn-jump paths from SS that have not yet reached EE and end in each class, an+1=an+bn,bn+1=an+cn,cn+1=bn, \begin{aligned} &a_{n+1} = a_n + b_n, \\ &b_{n+1} = a_n + c_n, \\ &c_{n+1} = b_n, \end{aligned} and exactly cnc_n paths reach EE for the first time on jump n+1.n + 1.

Starting from (a0,b0,c0)=(1,0,0),(a_0, b_0, c_0) = (1, 0, 0), the values of cnc_n for n=0,1,,11n = 0, 1, \ldots, 11 are 0,0, 0,0, 1,1, 1,1, 3,3, 4,4, 9,9, 14,14, 28,28, 47,47, 89,89, 155.155.

The number of sequences of at most 1212 jumps ending at EE is c0+c1++c11=351.c_0 + c_1 + \cdots + c_{11} = 351.

← Problem 13#13
Full Exam

Problem 14 in Other Years