Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2008 AIME I Problems/Problem 11"
m (→‎Solution)
Line 14: Line 14:
 
</cmath>
 
</cmath>
 
By counting, we find that <math>a_1 = 0, b_1 = 1, a_2 = 1, b_2 = 0</math>.  
 
By counting, we find that <math>a_1 = 0, b_1 = 1, a_2 = 1, b_2 = 0</math>.  
−
<cmath>\begin{tabular}{|r||r|r|||r||r|r|}
+
<cmath>\begin{array}{|r||r|r|||r||r|r|}
 
\hline
 
\hline
 
n & a_n & b_n & n & a_n & b_n\\
 
n & a_n & b_n & n & a_n & b_n\\
Line 33: Line 33:
 
14&80&92\\
 
14&80&92\\
 
\hline
 
\hline
−
\end{tabular}
+
\end{array}
 
</cmath>
 
</cmath>
 
Therefore, the number of such strings of length <math>14</math> is <math>a_{14} + b_{14} = \boxed{172}</math>.
 
Therefore, the number of such strings of length <math>14</math> is <math>a_{14} + b_{14} = \boxed{172}</math>.
Line 40: Line 40:
 
We replace "14" with "<math>2n</math>". We first note that we must have an even number of chunks of <math>B</math>'s, because of parity issues.  We then note that every chunk of <math>B</math>'s except the last one must end in the sequence <math>BAA</math>, since we need at least two <math>A</math>'s to separate it from the next chunk of <math>B</math>'s. The last chunk of <math>B</math>'s must, of course, end with a <math>B</math>.  Thus our sequence must look like this :
 
We replace "14" with "<math>2n</math>". We first note that we must have an even number of chunks of <math>B</math>'s, because of parity issues.  We then note that every chunk of <math>B</math>'s except the last one must end in the sequence <math>BAA</math>, since we need at least two <math>A</math>'s to separate it from the next chunk of <math>B</math>'s. The last chunk of <math>B</math>'s must, of course, end with a <math>B</math>.  Thus our sequence must look like this :
 
<cmath>
 
<cmath>
−
\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}} ,
+
\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} ,
 
</cmath>
 
</cmath>
 
where each box holds an even number of letters (possibly zero).
 
where each box holds an even number of letters (possibly zero).

Revision as of 16:30, 13 March 2015

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 an $A$, then it must have been formed by appending two $A$s to the end of a string of length $n-2$. If a sequence ends in a $B,$ it must have either been formed by appending one $B$ to a string of length $n-1$ ending in an $A$, or by appending two $B$s 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{array}{|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{array}\] 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} ,\] 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} .\] It follows that the total number of desirable sequences is \[\sum_k \binom{n + k + 1}{4k} .\] 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 (Problems • Answer Key • Resources)
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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2008_AIME_I_Problems/Problem_11&oldid=68832"