2008 AIME I Problems/Problem 11

Problem

Consider sequences that consist entirely of 's and 's and that have the property that every run of consecutive 's has even length, and every run of consecutive 's has odd length. Examples of such sequences are , , and , while is not such a sequence. How many such sequences have length 14?

Solution

Solution 1

Let and denote, respectively, the number of sequences of length ending in and . If a sequence ends in an , then it must have been formed by appending two s to the end of a string of length . If a sequence ends in , it must have either been formed by appending one to a string of length ending in an , or by appending two s to a string of length ending in a . Thus, we have the recursions By counting, we find that .

\[\begin{tabular}{|r||r|r|||r||r|r|}
\hline
n & a_n & b_n & n & a_n & b_n\\
\hline
1&0&1&
8&6&10\\
2&1&0&
9&11&11\\
3&1&2&
10&16&21\\
4&1&1&
11&22&27\\
5&3&3&
12&37&43\\
6&2&4&
13&49&64\\
7&6&5&
14&80&92\\
\hline
\end{tabular}\] (Error compiling LaTeX. Unknown error_msg)

Therefore, the number of such strings of length is .

Solution 2

We replace "14" with "". We first note that we must have an even number of chunks of 's, because of parity issues. We then note that every chunk of 's except the last one must end in the sequence , since we need at least two 's to separate it from the next chunk of 's. The last chunk of 's must, of course, end with a . Thus our sequence must look like this :

\[\boxed{\quad A\text{'s} \quad}} \boxed{\quad B\text{'s} \quad}} BAA \boxed{\quad A\text{'s} \quad}} \cdots \boxed{\quad B\text{'s} \quad}}BAA \boxed{\quad A\text{'s} \quad}} \boxed{\quad B\text{'s} \quad}} B \boxed{\quad A\text{'s} \quad}} ,\] (Error compiling LaTeX. Unknown error_msg)

where each box holds an even number of letters (possibly zero).

If we want a sequence with chunks of 's, then we have letters with which to fill the boxes. Since each box must have an even number of letters, we may put the letters in the boxes in pairs. Then we have pairs of letters to put into boxes. By a classic balls-and-bins argument, the number of ways to do this is It follows that the total number of desirable sequences is For , this evaluates as .