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$

Solución:

Nota $S(1) = 2,$ $S(2) = 4,$ $S(3) = 8.$ Toda sucesión válida termina en 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.$ Así $\begin{aligned} &S(n) = S(n-1) + S(n-2) \\ &\quad {}+ S(n-3). \end{aligned}$

Módulo $3,$ la sucesión $S(n)$ es periódica con periodo $13.$ Como $2015 = 13\cdot 155,$ $S(2015) \equiv S(13) \equiv 2 \pmod 3.$ Módulo $4,$ es periódica con periodo $4,$ y $2015 = 4\cdot 503 + 3,$ así que $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 lo 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 sequence $S(n)$ is periodic with period $13.$ Since $2015 = 13\cdot 155,$ $S(2015) \equiv S(13) \equiv 2 \pmod 3.$ Modulo $4,$ it is periodic with period $4,$ and $2015 = 4\cdot 503 + 3,$ so $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

Solución:

El Problema 22 en otros años