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$

Answer: D

Concepts:recursive counting modular arithmetic Chinese Remainder Theorem

Difficulty rating: 2270

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

Answer: D

Difficulty rating: 2270

Solution:

Problem 22 in Other Years