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

Latest revision as of 21:39, 28 November 2023

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 1a

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 1b

Let $a_n$ and $b_n$ denote, respectively, the number of sequences of length $n$ ending in $A$ and $B$ .

Additionally, let $t_n$ denote the total number of sequences of length $n$ . Then, $t_n=a_n+b_n$ , as the total amount of sequences of length $n$ consists of the sequences of length $n$ ending in $A$ and the sequences of length $n$ ending in $B$ . $\begin{align*} a_n &= a_{n-2} + b_{n-2}\\ b_n &= a_{n-1} + b_{n-2} \end{align*}$ The recursion for $a_n$ tells us that $a_n=a_{n-2}+b_{n-2}$ . However, this is also the definition for $t_{n-2}$ . Therefore, $a_n=t_{n-2}$ .

We also know from our recursion for $b_n$ that $b_n=a_{n-1}+b_{n-2}$ . Substituting for $a_n$ and $b_n$ into our recursion for $t_n$ gives us $t_n=t_{n-2}+a_{n-1}+b_{n-2}$ .

Furthermore, note that since $a_n=t_{n-2}$ , $a_{n-1}=t_{n-3}$ . Furthermore, using our definition for $t_{n-2}$ , we can rewrite $b_{n-2}$ as $t_{n-2}-a_{n-2}$ . Substituting for $a_{n-1}$ and $b_{n-2}$ into our recursion for $t_n$ gives us $t_n=t_{n-2}+t_{n-3}+t_{n-2}-a_{n-2}$ .

Finally, note that since $a_n=t_{n-2}$ , $a_{n-2}=t_{n-4}$ . Substituting for $a_{n-2}$ into our recursion for $t_n$ gives us $t_n=2t_{n-2}+t_{n-3}-t_{n-4}$ . We now have a recursion only in terms of $t$ .

By counting, we find that $t_1=1$ , $t_2=1$ , $t_3=3$ , and $t_4=2$ . $\begin{array}{|r|r||r|r|} \hline n & t_n & n & t_n\\ \hline 1&1&8&16\\ 2&1&9&22\\ 3&3&10&37\\ 4&2&11&49\\ 5&6&12&80\\ 6&6&13&113\\ 7&11&14&172\\ \hline \end{array}$

Therefore, the number of such sequences of length 14 is $\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}$ .

Solution 3

There must be an even amount of runs of consecutive $B$ s due to parity. Thus, we can split this sequence into the following cases: $A$ , $BAAB$ , $AABAAB$ , $BAABAA$ , $AABAABAA$ , $BAABAABAAB$ , $AABAABAABAAB$ , $BAABAABAABAA$ , and $AABAABAABAABAA$ , in which the amount of letters in one run does not necessarily represent the amount of letters there can be.

For the first case and the last case, there is only one possible sequence of letters.

For all other cases, we can insert two of the same letter at a time into a run that has the exact same letter. For example, for the second case, we can insert two $A$ s and make the sequence $BAAAAB$ . There are three "slots" in which we can insert two additional letters in, and we must insert five groups of new letters. By stars and bars, the number of ways for the second case is $\binom{7}{2}=21$ .

Applying this logic to all of the other cases gives us $\binom{7}{3}$ , $\binom{7}{3}$ , $\binom{7}{4}$ , $\binom{8}{6}$ , $\binom{8}{1}$ , and $\binom{8}{1}$ . Adding 1+ $\binom{7}{2}$ + $\binom{7}{3}$ + $\binom{7}{3}$ + $\binom{7}{4}$ + $\binom{8}{6}$ + $\binom{8}{1}$ + $\binom{8}{1}$ gives us the answer $\boxed{172}$ .

@@ Line 1: / Line 1: @@
+__TOC__
 == 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, and every run of consecutive <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__
+== Solution 1a ==
-== Solution ==
-=== Solution 1 ===
 Let <math>a_n</math> and <math>b_n</math> denote, respectively, the number of sequences of length <math>n</math> ending in <math>A</math> and <math>B</math>. If a sequence ends in an <math>A</math>, then it must have been formed by appending two <math>A</math>s to the end of a string of length <math>n-2</math>. If a sequence ends in a <math>B,</math> it must have either been formed by appending one <math>B</math> to a string of length <math>n-1</math> ending in an <math>A</math>, or by appending two <math>B</math>s to a string of length <math>n-2</math> ending in a <math>B</math>. Thus, we have the [[recursion]]s
 <cmath>
@@ Line 14: / Line 13: @@
 </cmath>
 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
 n & a_n & b_n & n & a_n & b_n\\
@@ Line 33: / Line 32: @@
 &80&92\\
 \hline
-\end{tabular}
+\end{array}
 </cmath>
 Therefore, the number of such strings of length <math>14</math> is <math>a_{14} + b_{14} = \boxed{172}</math>.
-=== Solution 2 ===
+== Solution 1b ==
+Let <math>a_n</math> and <math>b_n</math> denote, respectively, the number of sequences of length <math>n</math> ending in <math>A</math> and <math>B</math>.
+Additionally, let <math>t_n</math> denote the total number of sequences of length <math>n</math>. Then, <math>t_n=a_n+b_n</math>, as the total amount of sequences of length <math>n</math> consists of the sequences of length <math>n</math> ending in <math>A</math> and the sequences of length <math>n</math> ending in <math>B</math>.
+<cmath>
+\begin{align*}
+a_n &= a_{n-2} + b_{n-2}\\
+b_n &= a_{n-1} + b_{n-2}
+\end{align*}
+</cmath>
+The recursion for <math>a_n</math> tells us that <math>a_n=a_{n-2}+b_{n-2}</math>. However, this is also the definition for <math>t_{n-2}</math>. Therefore, <math>a_n=t_{n-2}</math>.
+We also know from our recursion for <math>b_n</math> that <math>b_n=a_{n-1}+b_{n-2}</math>. Substituting for <math>a_n</math> and <math>b_n</math> into our recursion for <math>t_n</math> gives us <math>t_n=t_{n-2}+a_{n-1}+b_{n-2}</math>.
+Furthermore, note that since <math>a_n=t_{n-2}</math>, <math>a_{n-1}=t_{n-3}</math>. Furthermore, using our definition for <math>t_{n-2}</math>, we can rewrite <math>b_{n-2}</math> as <math>t_{n-2}-a_{n-2}</math>. Substituting for <math>a_{n-1}</math> and <math>b_{n-2}</math> into our recursion for <math>t_n</math> gives us <math>t_n=t_{n-2}+t_{n-3}+t_{n-2}-a_{n-2}</math>.
+Finally, note that since <math>a_n=t_{n-2}</math>, <math>a_{n-2}=t_{n-4}</math>. Substituting for <math>a_{n-2}</math> into our recursion for <math>t_n</math> gives us <math>t_n=2t_{n-2}+t_{n-3}-t_{n-4}</math>. We now have a recursion only in terms of <math>t</math>.
+By counting, we find that <math>t_1=1</math>, <math>t_2=1</math>, <math>t_3=3</math>, and <math>t_4=2</math>.
+<cmath>\begin{array}{|r|r||r|r|}
+\hline
+n & t_n & n & t_n\\
+\hline
+&1&8&16\\
+&1&9&22\\
+&3&10&37\\
+&2&11&49\\
+&6&12&80\\
+&6&13&113\\
+&11&14&172\\
+\hline
+\end{array}
+</cmath>
+Therefore, the number of such sequences of length 14 is <math>\boxed{172}</math>.
+== Solution 2 ==
 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>
-\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>
 where each box holds an even number of letters (possibly zero).
-If we want a sequence with <math>2k</math> chunks of <math>B</math>'s, then we have <math>(2n - 6k + 2)</math> 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 <math>(n - 3k + 1)</math> pairs of letters to put into <math>4k + 1</math> boxes. By a classic balls-and-bins argument, the number of ways to do this is
+If we want a sequence with <math>2k</math> chunks of <math>B</math>'s, then we have <math>(2n - 6k + 2)</math> 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 <math>(n - 3k + 1)</math> pairs of letters to put into <math>4k + 1</math> boxes. By a classic [[balls-and-bins]] argument, the number of ways to do this is
 <cmath>
 \binom{n + k + 1}{4k} .
@@ Line 53: / Line 88: @@
 </cmath>
 For <math>n = 7</math>, this evaluates as <math>\binom{8}{0} + \binom{9}{4} + \binom{10}{8} = 1 + 126 + 45 = \boxed{172}</math>.
+==Solution 3==
+There must be an even amount of runs of consecutive <math>B</math>s due to parity. Thus, we can split this sequence into the following cases: <math>A</math>, <math>BAAB</math>, <math>AABAAB</math>, <math>BAABAA</math>, <math>AABAABAA</math>, <math>BAABAABAAB</math>, <math>AABAABAABAAB</math>, <math>BAABAABAABAA</math>, and <math>AABAABAABAABAA</math>, in which the amount of letters in one run does not necessarily represent the amount of letters there can be.
+For the first case and the last case, there is only one possible sequence of letters.
+For all other cases, we can insert two of the same letter at a time into a run that has the exact same letter. For example, for the second case, we can insert two <math>A</math>s and make the sequence <math>BAAAAB</math>. There are three "slots" in which we can insert two additional letters in, and we must insert five groups of new letters. By [[stars and bars]], the number of ways for the second case is <math>\binom{7}{2}=21</math>.
+Applying this logic to all of the other cases gives us <math>\binom{7}{3}</math>, <math>\binom{7}{3}</math>, <math>\binom{7}{4}</math>, <math>\binom{8}{6}</math>, <math>\binom{8}{1}</math>, and <math>\binom{8}{1}</math>. Adding 1+<math>\binom{7}{2}</math>+<math>\binom{7}{3}</math>+<math>\binom{7}{3}</math>+<math>\binom{7}{4}</math>+<math>\binom{8}{6}</math>+<math>\binom{8}{1}</math>+<math>\binom{8}{1}</math> gives us the answer <math>\boxed{172}</math>.
 == See also ==
@@ Line 58: / Line 102: @@
 [[Category:Intermediate Combinatorics Problems]]
+{{MAA Notice}}

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

Page

Toolbox

Search