Problem:
For each positive integer , let be the number of sequences of length consisting solely of the letters and , with no more than three s in a row and no more than three s in a row. What is the remainder when is divided by ?
Answer Choices:
A.
B.
C.
D.
E.
Solution:
Note that , and . Call a sequence with and entries valid if it does not contain 4 or more consecutive symbols that are the same. For , every valid sequence of length can be extended to a valid sequence of length by appending a symbol different from its last symbol. Similarly, valid sequences of length or can be extended
to valid sequences of length by appending either two or three equal symbols different from its last symbol. Note that all of these sequences are pairwise distinct. Conversely, every valid sequence of length ends with either one, two, or three equal consecutive symbols. Removal of these equal symbols at the end produces every valid sequence of length , or , respectively. Thus . This recursive formula implies that the remainders modulo 3 of the sequence for are
Thus the sequence is periodic with period-length 13 . Because , it follows that . Similarly, the remainders modulo 4 of the sequence for are . Thus the sequence is periodic with period-length 4 . Because , it follows that . Therefore for some integer , and . Hence and .
The problems on this page are the property of the MAA's American Mathematics Competitions