Difference between revisions of "Mock AIME 1 2006-2007 Problems/Problem 11"
m |
|||
Line 13: | Line 13: | ||
We come up with a different recursion. Overcounting, we can add either a 0 or a 1 onto any string of length n. However, we have to back out the times we've added a third 0. In that case, the previous two will be 0, the one before that will be one, and preceeding that can be any string of length <math>n-4</math>. We thus have the recursion <math>{S}_n=2{S}_{n-1}-{S}_{n-4}</math>. We proceed as above. | We come up with a different recursion. Overcounting, we can add either a 0 or a 1 onto any string of length n. However, we have to back out the times we've added a third 0. In that case, the previous two will be 0, the one before that will be one, and preceeding that can be any string of length <math>n-4</math>. We thus have the recursion <math>{S}_n=2{S}_{n-1}-{S}_{n-4}</math>. We proceed as above. | ||
− | *[[Mock AIME 1 2006-2007/Problem 10 | Previous Problem]] | + | *[[Mock AIME 1 2006-2007 Problems/Problem 10 | Previous Problem]] |
− | *[[Mock AIME 1 2006-2007/Problem 12 | Next Problem]] | + | *[[Mock AIME 1 2006-2007 Problems/Problem 12 | Next Problem]] |
*[[Mock AIME 1 2006-2007]] | *[[Mock AIME 1 2006-2007]] | ||
[[Category:Intermediate Combinatorics Problems]] | [[Category:Intermediate Combinatorics Problems]] |
Latest revision as of 15:51, 3 April 2012
Problem
Let be the set of strings with only 0's or 1's with length
such that any 3 adjacent place numbers sum to at least 1. For example,
works, but
does not. Find the number of elements in
.
Solution
We will solve this problem by constructing a recursion satisfied by .
Let be the number of such strings of length
ending in 1,
be the number of such strings of length
ending in a single 0 and
be the number of such strings of length
ending in a double zero. Then
and
.
Note that . For
we have
(since we may add a 1 to the end of any valid string of length
to get a valid string of length
),
(since every valid string ending in 10 can be arrived at by adding a 0 to a string ending in 1) and
(since every valid string ending in 100 can be arrived at by adding a 0 to a string ending in 10).
Thus . Then using the initial values
we can easily compute that
.
Solution 2
We come up with a different recursion. Overcounting, we can add either a 0 or a 1 onto any string of length n. However, we have to back out the times we've added a third 0. In that case, the previous two will be 0, the one before that will be one, and preceeding that can be any string of length . We thus have the recursion
. We proceed as above.