Difference between revisions of "2008 AIME I Problems/Problem 11"

m (<blank edit> Solution 2 credit to Boy Soprano II)
(Problem)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
Consider sequences that consist entirely of <math>A</math>'s and <math>B</math>'s and that have the property that every run of consecutive <math>A</math>'s has even length. Examples of such sequences are <math>AA</math>, <math>B</math>, and <math>AABAA</math>, while <math>BBAB</math> is not such a sequence. How many such sequences have length 14?
+
Consider sequences that consist entirely of <math>A</math>'s and <math>B</math>'s and that have the property that every run of consecutive <math>A</math>'s has even length, and every run of consecuitve <math>B</math>'s has odd length. Examples of such sequences are <math>AA</math>, <math>B</math>, and <math>AABAA</math>, while <math>BBAB</math> is not such a sequence. How many such sequences have length 14?
  
 
__TOC__
 
__TOC__
 +
 
== Solution ==
 
== Solution ==
 
=== Solution 1 ===
 
=== Solution 1 ===

Revision as of 19:12, 4 February 2009

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 consecuitve $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|}
\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 $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\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 $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}$.

See also

2008 AIME I (ProblemsAnswer KeyResources)
Preceded by
Problem 10
Followed by
Problem 12
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
All AIME Problems and Solutions