Question

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$

Solution:

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 $S(n) = S(n-1) + S(n-2) + S(n-3).$

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 Problem 22

Solution:

Problem 22 in Other Years