2015 AMC 12A Problema 22

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

Pista pequeña:

Una sucesión válida termina en una racha de

1,

2,

o

3

letras iguales, lo que da

S(n) = S(n-1)

+ S(n-2)

+ S(n-3)

A valid sequence ends in a run of

1,

2,

or

3

equal letters, giving

S(n) = S(n-1)

+ S(n-2)

+ S(n-3)

Pista grande:

Reduce la recurrencia módulo

3

y módulo

4

por separado para hallar su periodo

Reduce the recurrence modulo

3

and modulo

4

separately to find its period

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.