2018 AIME I 第 14 题

先试着解答 2018 AIME I 第 14 题,然后核对你的答案与精心整理的解答,解答来自 LIVE by Po-Shen Loh。你也可以参加完整限时模拟考试、查看全部 2018 AIME I 解答,或核对答案

所有题目均经美国数学协会(MAA)官方合法授权使用。

14.

SP1P2P3EP4P5SP_1P_2P_3EP_4P_5 为一个七边形。一只青蛙从顶点 SS 开始跳跃。除 EE 外,从七边形的任意顶点,青蛙都可以跳到两个相邻顶点之一。当它到达顶点 EE 时,就停止并停在那里。求不超过 1212 次跳跃且最终到达 EE 的不同跳跃序列个数。

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.

答案:351
知识点:递推计数对称性
难度评级:3160
解答:

把顶点分为 A={S,P1}\mathcal{A} = \{S, P_1\}B={P2,P5}\mathcal{B} = \{P_2, P_5\}C={P3,P4}\mathcal{C} = \{P_3, P_4\}A\mathcal{A} 中每个顶点邻接一个 A\mathcal{A} 中的点和一个 B\mathcal{B} 中的点;B\mathcal{B} 中每个顶点邻接一个 A\mathcal{A} 中的点和一个 C\mathcal{C} 中的点;C\mathcal{C} 中每个顶点邻接一个 B\mathcal{B} 中的点和吸收顶点 EE。因此若 ana_nbnb_ncnc_n 计数从 SS 出发、尚未到达 EE 且经过 nn 跳后停在各类中的路径数,则 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} 并且恰有 cnc_n 条路径会在第 n+1n + 1 跳首次到达 EE

(a0,b0,c0)=(1,0,0)(a_0, b_0, c_0) = (1, 0, 0) 开始,n=0,1,,11n = 0, 1, \ldots, 11 时的 cnc_n 依次为 000011113344991414282847478989155155

不超过 1212 跳且到达 EE 的序列数为 c0+c1++c11=351c_0 + c_1 + \cdots + c_{11} = 351

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.

← 第 13 题#13
完整试卷

其他年份的第 14 题