Question

Para cada entero positivo $n,$ sea $S(n)$ el número de sucesiones de longitud $n$ formadas únicamente por las letras $A$ y $B,$ con no más de tres $A$ seguidas y no más de tres $B$ seguidas. ¿Cuál es el residuo cuando $S(2015)$ se divide entre $12$ ?

For each positive integer $n,$ let $S(n)$ be the number of sequences of length $n$ consisting solely of the letters $A$ and $B,$ with no more than three $A$ s in a row and no more than three $B$ s in a row. What is the remainder when $S(2015)$ is divided by $12?$

$0$

$4$

$6$

$8$

$10$

Respuesta: D

Conceptos:conteo recursivo aritmética modular Teorema chino del resto

Nivel de dificultad: 2270

Solución:

Observemos que $S(1) = 2,$ $S(2) = 4,$ $S(3) = 8.$ Toda sucesión válida termina con una racha de una, dos o tres letras iguales; al quitar esa racha queda una sucesión válida de longitud $n-1,$ $n-2,$ o $n-3.$ Por tanto, $\begin{aligned} &S(n) = S(n-1) + S(n-2) \\ &\quad {}+ S(n-3). \end{aligned}$

Módulo $3,$ los primeros $13$ términos son $2,1,2,2,2,0,1,0,1,2,0,0,2.$ Los tres siguientes son $2,1,2,$ que reproducen el estado inicial, así que la recurrencia se repite con período $13.$ Como $2015 = 13\cdot 155,$ se sigue que $S(2015) \equiv S(13) \equiv 2 \pmod 3.$

Módulo $4,$ los términos se repiten como $2,0,0,2,$ porque el estado de tres términos posterior a esos cuatro vuelve a ser $(2,0,0).$ Por tanto, el período es $4.$ Como $2015 = 4\cdot 503 + 3,$ tenemos $S(2015) \equiv S(3) \equiv 0 \pmod 4.$

Escribiendo $S(2015) = 4k,$ la condición $4k \equiv 2 \pmod 3$ da $k \equiv 2 \pmod 3,$ así que $S(2015) \equiv 8 \pmod{12}.$

Por tanto, la respuesta correcta es D.

Note $S(1) = 2,$ $S(2) = 4,$ $S(3) = 8.$ Every valid sequence ends in a run of one, two, or three equal letters; removing that run leaves a valid sequence of length $n-1,$ $n-2,$ or $n-3.$ Thus $\begin{aligned} &S(n) = S(n-1) + S(n-2) \\ &\quad {}+ S(n-3). \end{aligned}$

Modulo $3,$ the first $13$ terms are $2,1,2,2,2,0,1,0,1,2,0,0,2.$ The next three terms are $2,1,2,$ which reproduce the initial state, so the recurrence repeats with period $13.$ Since $2015 = 13\cdot 155,$ it follows that $S(2015) \equiv S(13) \equiv 2 \pmod 3.$

Modulo $4,$ the terms repeat as $2,0,0,2,$ because the next three-term state after these four terms is again $(2,0,0).$ Thus the period is $4.$ As $2015 = 4\cdot 503 + 3,$ we have $S(2015) \equiv S(3) \equiv 0 \pmod 4.$

Writing $S(2015) = 4k,$ the condition $4k \equiv 2 \pmod 3$ gives $k \equiv 2 \pmod 3,$ so $S(2015) \equiv 8 \pmod{12}.$

Thus, the correct answer is D.

2015 AMC 12A Problema 22

Respuesta: D

Nivel de dificultad: 2270

Solución:

El Problema 22 en otros años