Difference between revisions of "2008 AIME I Problems/Problem 11"
Mathgeek2006 (talk | contribs) m (→Solution) |
Phi ftw1618 (talk | contribs) (→Solution) |
||
Line 53: | Line 53: | ||
</cmath> | </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>. | 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 == | == See also == |
Revision as of 10:18, 2 December 2016
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
Solution 1
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 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.