2018 AIME I Problem 14

Below is the professionally curated solution for Problem 14 of the 2018 AIME I, 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 of the real AMC 8, AMC 10, AMC 12, and AIME problems in our complete solution collection are used with official legal permission of the Mathematical Association of America (MAA).

Concepts:recursive countingsymmetry

Difficulty rating: 3160

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.

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,a_{n+1} = a_n + b_n, \qquad b_{n+1} = a_n + c_n, \qquad c_{n+1} = b_n, 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,1,1,3,4,9,14,28,47,89,155.0, 0, 1, 1, 3, 4, 9, 14, 28, 47, 89, 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 13Full ExamProblem 15

Problem 14 in Other Years