Difference between revisions of "Mock AIME 1 2006-2007 Problems/Problem 11"
Dgreenb801 (talk | contribs) (→Solution) |
Dgreenb801 (talk | contribs) (→Solution) |
||
| Line 10: | Line 10: | ||
Thus <math>\mathcal{S}_n = A_1(n) + A_2(n) + A_3(n) = \mathcal{S}_{n - 1} + A_1(n - 1) + A_2(n - 1) = \mathcal{S}_{n -1} + \mathcal{S}_{n - 2} + A_1(n - 2) = \mathcal{S}_{n - 1} + \mathcal{S}_{n -2} + \mathcal{S}_{n - 3}</math>. Then using the initial values <math>\mathcal{S}_1 = 2, \mathcal{S}_2 = 4, \mathcal{S}_3 = 7</math> we can easily compute that <math>\mathcal{S}_{11} = 927</math>. | Thus <math>\mathcal{S}_n = A_1(n) + A_2(n) + A_3(n) = \mathcal{S}_{n - 1} + A_1(n - 1) + A_2(n - 1) = \mathcal{S}_{n -1} + \mathcal{S}_{n - 2} + A_1(n - 2) = \mathcal{S}_{n - 1} + \mathcal{S}_{n -2} + \mathcal{S}_{n - 3}</math>. Then using the initial values <math>\mathcal{S}_1 = 2, \mathcal{S}_2 = 4, \mathcal{S}_3 = 7</math> we can easily compute that <math>\mathcal{S}_{11} = 927</math>. | ||
---- | ---- | ||
| + | ==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 <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/Problem 10 | Previous Problem]] | ||
Revision as of 22:20, 18 January 2009
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.
