2008 AIME I Problems/Problem 11

From AoPSWiki

Problem

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

Solution

Solution 1

Let $a_n$ and $b_n$ denote, respectively, the number of sequences of length $n$ ending in A and B. If a sequence ends in a A, then it must have been formed by appending two As to the end of a string of length $n-2$ . If a sequence ends in B, it must have either been formed by appending one B to a string of length $n-1$ ending in a A, or by appending two Bs to a string of length $n-2$ ending in a B. Thus, we have the recursions $\begin{align*}a_n &= a_{n-2} + b_{n-2}\\b_n &= a_{n-1} + b_{n-2} \end{align*}$ By counting, we find that $a_1 = 0, b_1 = 1, a_2 = 1, b_2 = 0$ . $\begin{tabular}{|r||r|r|||r||r|r|}\hlinen & a_n & b_n & n & a_n & b_n\\\hline1&0&1&8&6&am...$ Therefore, the number of such strings of length $14$ is $a_{14} + b_{14} = \boxed{172}$ .

Solution 2

We replace "14" with " $2n$ ". We first note that we must have an even number of chunks of $B$ 's, because of parity issues. We then note that every chunk of $B$ 's except the last one must end in the sequence $BAA$ , since we need at least two $A$ 's to separate it from the next chunk of $B$ 's. The last chunk of $B$ 's must, of course, end with a $B$ . 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\tex...$ where each box holds an even number of letters (possibly zero).

If we want a sequence with $2k$ chunks of $B$ 's, then we have $(2n - 6k + 2)$ 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 $(n - 3k + 1)$ pairs of letters to put into $4k + 1$ boxes. By a classic balls-and-bins argument, the number of ways to do this is $\binom{n + k + 1}{4k + 1} .$ It follows that the total number of desirable sequences is $\sum_k \binom{n + k + 1}{4k + 1} .$ For $n = 7$ , this evaluates as $\binom{8}{0} + \binom{9}{4} + \binom{10}{8} = 1 + 126 + 45 = \boxed{172}$ .

2008 AIME I (Problems • Resources)
Preceded by Problem 10	Followed by Problem 12
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15

Personal tools

Navigation

Search

Toolbox