Question

Sea $SP_1P_2P_3EP_4P_5$ un heptágono. Una rana empieza a saltar en el vértice $S.$ Desde cualquier vértice del heptágono excepto $E,$ la rana puede saltar a cualquiera de los dos vértices adyacentes. Cuando llega al vértice $E,$ la rana se detiene y permanece allí. Halle el número de sucesiones distintas de saltos de no más de $12$ saltos que terminan en $E.$

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

Respuesta

Solución:

Agrupe los vértices en clases $\mathcal{A} = \{S, P_1\},$ $\mathcal{B} = \{P_2, P_5\},$ y $\mathcal{C} = \{P_3, P_4\}.$ Cada vértice de $\mathcal{A}$ se une a un vértice de $\mathcal{A}$ y a uno de $\mathcal{B};$ cada vértice de $\mathcal{B}$ se une a uno de $\mathcal{A}$ y a uno de $\mathcal{C};$ y cada vértice de $\mathcal{C}$ se une a uno de $\mathcal{B}$ y al vértice absorbente $E.$ Por lo tanto, si $a_n,$ $b_n,$ $c_n$ cuentan los caminos de $n$ saltos desde $S$ que aún no han llegado a $E$ y terminan en cada clase, $\begin{aligned} &a_{n+1} = a_n + b_n, \\ &b_{n+1} = a_n + c_n, \\ &c_{n+1} = b_n, \end{aligned}$ y exactamente $c_n$ caminos llegan a $E$ por primera vez en el salto $n + 1.$

Partiendo de $(a_0, b_0, c_0) = (1, 0, 0),$ los valores de $c_n$ para $n = 0, 1, \ldots, 11$ son $0,$ $0,$ $1,$ $1,$ $3,$ $4,$ $9,$ $14,$ $28,$ $47,$ $89,$ $155.$

El número de sucesiones de a lo más $12$ saltos que terminan en $E$ es $c_0 + c_1 + \cdots + c_{11} = 351.$

Group the vertices into classes $\mathcal{A} = \{S, P_1\},$ $\mathcal{B} = \{P_2, P_5\},$ and $\mathcal{C} = \{P_3, P_4\}.$ Each vertex of $\mathcal{A}$ adjoins one vertex of $\mathcal{A}$ and one of $\mathcal{B};$ each vertex of $\mathcal{B}$ adjoins one of $\mathcal{A}$ and one of $\mathcal{C};$ and each vertex of $\mathcal{C}$ adjoins one of $\mathcal{B}$ and the absorbing vertex $E.$ Hence if $a_n,$ $b_n,$ $c_n$ count the $n$ -jump paths from $S$ that have not yet reached $E$ and end in each class, $\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 $c_n$ paths reach $E$ for the first time on jump $n + 1.$

Starting from $(a_0, b_0, c_0) = (1, 0, 0),$ the values of $c_n$ for $n = 0, 1, \ldots, 11$ are $0,$ $0,$ $1,$ $1,$ $3,$ $4,$ $9,$ $14,$ $28,$ $47,$ $89,$ $155.$

The number of sequences of at most $12$ jumps ending at $E$ is $c_0 + c_1 + \cdots + c_{11} = 351.$

2018 AIME I Problema 14

Solución:

El Problema 14 en otros años