2008 AIME I Problems/Problem 11
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
.
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.