Question

Considera las sucesiones que constan enteramente de $A$ y $B$ y que tienen la propiedad de que toda racha de $A$ consecutivas tiene longitud par, y toda racha de $B$ consecutivas tiene longitud impar. Ejemplos de tales sucesiones son $AA,$ $B,$ y $AABAA,$ mientras que $BBAB$ no es una sucesión de este tipo. ¿Cuántas sucesiones de este tipo tienen longitud $14$ ?

Consider sequences that consist entirely of $A$ ’s and $B$ ’s and that have the property that every run of consecutive $A$ ’s has even length, and every run of consecutive $B$ ’s has odd length. Examples of such sequences are $AA,$ $B,$ and $AABAA,$ while $BBAB$ is not such a sequence. How many such sequences have length $14?$

Respuesta

Respuesta: 172

Conceptos:conteo recursivo arreglos con restricciones paridad

Nivel de dificultad: 2920

Pista pequeña:

Clasifica según la primera letra: una sucesión válida que empieza con $A$ debe comenzar con $AA$ seguido de cualquier sucesión válida (posiblemente vacía)

Classify by the first letter: a valid sequence starting with $A$ must begin with $AA$ followed by any valid (possibly empty) sequence

Pista grande:

Con $a_n, b_n$ contando las sucesiones válidas de longitud $n$ que empiezan con $A$ o $B:$ $a_{n+2} = a_n + b_n$ y $b_{n+2} = a_{n+1} + b_n.$ Itera hasta $n = 14.$

With $a_n, b_n$ counting valid length- $n$ sequences starting with $A$ or $B:$ $a_{n+2} = a_n + b_n$ and $b_{n+2} = a_{n+1} + b_n.$ Iterate up to $n = 14.$

Solución:

Sean $a_n$ y $b_n$ el número de sucesiones válidas de longitud $n$ que empiezan con $A$ y con $B.$ Una sucesión que empieza con $A$ comienza con $AA$ seguido de cualquier sucesión válida de longitud $n - 2$ (posiblemente vacía), así que $a_{n+2} = a_n + b_n,$ donde la sucesión vacía cuenta una vez. Una sucesión que empieza con $B$ comienza o bien con una sola $B$ seguida de una sucesión que empieza con $A,$ o bien con $BB$ seguido de una sucesión que empieza con $B,$ así que $b_{n+2} = a_{n+1} + b_n.$

Partiendo de $(a_1, b_1) = (0, 1)$ y $(a_2, b_2) = (1, 0),$ los pares $(a_n, b_n)$ para $n = 3, 4, \ldots, 14$ son $\begin{aligned} &(1, 2),\ (1, 1),\ (3, 3),\ \\ &(2, 4),\ (6, 5),\ (6, 10),\ \\ &(11, 11),\ (16, 21),\ (22, 27),\ \\ &(37, 43),\ (49, 64),\ (80, 92). \end{aligned}$

El número de sucesiones válidas de longitud $14$ es $80 + 92 = 172.$

Let $a_n$ and $b_n$ count valid sequences of length $n$ beginning with $A$ and with $B.$ A sequence beginning with $A$ starts with $AA$ followed by any valid sequence of length $n - 2$ (possibly empty), so $a_{n+2} = a_n + b_n,$ where the empty sequence counts once. A sequence beginning with $B$ starts either with a single $B$ followed by a sequence beginning with $A,$ or with $BB$ followed by a sequence beginning with $B,$ so $b_{n+2} = a_{n+1} + b_n.$

Starting from $(a_1, b_1) = (0, 1)$ and $(a_2, b_2) = (1, 0),$ the pairs $(a_n, b_n)$ for $n = 3, 4, \ldots, 14$ are $\begin{aligned} &(1, 2),\ (1, 1),\ (3, 3),\ \\ &(2, 4),\ (6, 5),\ (6, 10),\ \\ &(11, 11),\ (16, 21),\ (22, 27),\ \\ &(37, 43),\ (49, 64),\ (80, 92). \end{aligned}$

The number of valid sequences of length $14$ is $80 + 92 = 172.$

2008 AIME I Problema 11

Respuesta: 172

Nivel de dificultad: 2920

Pista pequeña:

Pista grande:

Solución:

El Problema 11 en otros años