2015 AMC 12A Problem 22

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.