Difference between revisions of "2008 AIME I Problems/Problem 11"
(→Solutions) |
m |
||
(9 intermediate revisions by 4 users not shown) | |||
Line 1: | Line 1: | ||
+ | __TOC__ | ||
+ | |||
== 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, 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? | 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? | ||
− | + | == Solution 1a == | |
− | |||
− | |||
− | |||
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 | 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> | <cmath> | ||
Line 37: | Line 36: | ||
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>. | ||
− | + | == 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>. | 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>. | 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> | <cmath> | ||
\begin{align*} | \begin{align*} | ||
a_n &= a_{n-2} + b_{n-2}\ | a_n &= a_{n-2} + b_{n-2}\ | ||
− | b_n &= a_{n-1} + b_{n-2} | + | b_n &= a_{n-1} + b_{n-2} |
\end{align*} | \end{align*} | ||
</cmath> | </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>. | 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- | + | 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>. | 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, t_2=1, t_3=3, t_4=2</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|} | + | <cmath>\begin{array}{|r|r||r|r|} |
− | \hline | + | \hline |
− | n & t_n & n & t_n\ | + | n & t_n & n & t_n\ |
− | \hline | + | \hline |
− | 1&1&8&16\ | + | 1&1&8&16\ |
2&1&9&22\ | 2&1&9&22\ | ||
− | 3&3&10&37\ | + | 3&3&10&37\ |
− | 4&2&11&49\ | + | 4&2&11&49\ |
− | 5&6&12&80\ | + | 5&6&12&80\ |
− | 6&6&13&113\ | + | 6&6&13&113\ |
− | 7&11&14&172\ | + | 7&11&14&172\ |
\hline | \hline | ||
\end{array} | \end{array} | ||
</cmath> | </cmath> | ||
+ | |||
Therefore, the number of such sequences of length 14 is <math>\boxed{172}</math>. | 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 : | 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> | ||
Line 81: | Line 79: | ||
where each box holds an even number of letters (possibly zero). | 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> | <cmath> | ||
\binom{n + k + 1}{4k} . | \binom{n + k + 1}{4k} . | ||
Line 91: | Line 89: | ||
For <math>n = 7</math>, this evaluates as <math>\binom{8}{0} + \binom{9}{4} + \binom{10}{8} = 1 + 126 + 45 = \boxed{172}</math>. | 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. | 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 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>. | + | 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>. | 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>. |
Latest revision as of 21:39, 28 November 2023
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 1a
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 a 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 . Therefore, the number of such strings of length is .
Solution 1b
Let and denote, respectively, the number of sequences of length ending in and .
Additionally, let denote the total number of sequences of length . Then, , as the total amount of sequences of length consists of the sequences of length ending in and the sequences of length ending in . The recursion for tells us that . However, this is also the definition for . Therefore, .
We also know from our recursion for that . Substituting for and into our recursion for gives us .
Furthermore, note that since , . Furthermore, using our definition for , we can rewrite as . Substituting for and into our recursion for gives us .
Finally, note that since , . Substituting for into our recursion for gives us . We now have a recursion only in terms of .
By counting, we find that , , , and .
Therefore, the number of such sequences of length 14 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 : 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 .
Solution 3
There must be an even amount of runs of consecutive s due to parity. Thus, we can split this sequence into the following cases: , , , , , , , , and , 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 s and make the sequence . 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 .
Applying this logic to all of the other cases gives us , , , , , and . Adding 1+++++++ gives us the answer .
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.