AMC12 2015 12A, Problem 22

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$?

Solution: We can start off by finding patterns in $S(n)$. When we calculate a few values we realize either from performing the calculation or because the calculation was performed in the exact same way that $S(n) = 2^n - 2((n_4)- (n_5) \dots (n_n))$. Rearranging the expression we realize that the terms aside from $2^{2015}$ are congruent to $0$ mod $12$(Just put the equation in terms of 2^{2015} and the four combinations excluded and calculate the combinations mod $12$). Using patterns we can see that $2^{2015}$ is congruent to $8$ mod $12$. Therefore $\fbox{8}$ is our answer.

Answer: 8