Difference between revisions of "Mock AIME 1 2006-2007 Problems/Problem 11"

m (spelling)
m
 
(3 intermediate revisions by 2 users not shown)
Line 4: Line 4:
 
We will solve this problem by constructing a [[recursion]] satisfied by <math>\mathcal{S}_n</math>.
 
We will solve this problem by constructing a [[recursion]] satisfied by <math>\mathcal{S}_n</math>.
  
Let <math>\displaystyle A_1(n)</math> be the number of such strings of length <math>n</math> ending in 1, <math>A_2(n)</math> be the number of such strings of length <math>n</math> ending in a single 0 and <math>A_3(n)</math> be the number of such strings of length <math>n</math> ending in a double zero.  Then <math>A_1(1) = 1, A_2(1) = 1, A_3(1) = 0, A_1(2) = 2, A_2(2) = 1</math> and <math>A_3(2) = 1</math>.   
+
Let <math>A_1(n)</math> be the number of such strings of length <math>n</math> ending in 1, <math>A_2(n)</math> be the number of such strings of length <math>n</math> ending in a single 0 and <math>A_3(n)</math> be the number of such strings of length <math>n</math> ending in a double zero.  Then <math>A_1(1) = 1, A_2(1) = 1, A_3(1) = 0, A_1(2) = 2, A_2(2) = 1</math> and <math>A_3(2) = 1</math>.   
  
 
Note that <math>\mathcal{S}_n = A_1(n) + A_2(n) + A_3(n)</math>.  For <math>n \geq 2</math> we have <math>A_1(n) = \mathcal{S}_{n - 1} = A_1(n - 1) + A_2(n - 1) + A_3(n - 1)</math> (since we may add a 1 to the end of any valid string of length <math>n - 1</math> to get a valid string of length <math>n</math>), <math>A_2(n) = A_1(n -1)</math> (since every valid string ending in 10 can be arrived at by adding a 0 to a string ending in 1) and <math>A_3(n) = A_2(n - 1)</math> (since every valid string ending in 100 can be arrived at by adding a 0 to a string ending in 10).
 
Note that <math>\mathcal{S}_n = A_1(n) + A_2(n) + A_3(n)</math>.  For <math>n \geq 2</math> we have <math>A_1(n) = \mathcal{S}_{n - 1} = A_1(n - 1) + A_2(n - 1) + A_3(n - 1)</math> (since we may add a 1 to the end of any valid string of length <math>n - 1</math> to get a valid string of length <math>n</math>), <math>A_2(n) = A_1(n -1)</math> (since every valid string ending in 10 can be arrived at by adding a 0 to a string ending in 1) and <math>A_3(n) = A_2(n - 1)</math> (since every valid string ending in 100 can be arrived at by adding a 0 to a string ending in 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 = 1, \mathcal{S}_2 = 2, \mathcal{S}_3 = 4</math> we can easily compute that <math>\mathcal{S}_{11} = 504</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 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 $\mathcal{S}_{n}$ be the set of strings with only 0's or 1's with length $n$ such that any 3 adjacent place numbers sum to at least 1. For example, $00100$ works, but $10001$ does not. Find the number of elements in $\mathcal{S}_{11}$.

Solution

We will solve this problem by constructing a recursion satisfied by $\mathcal{S}_n$.

Let $A_1(n)$ be the number of such strings of length $n$ ending in 1, $A_2(n)$ be the number of such strings of length $n$ ending in a single 0 and $A_3(n)$ be the number of such strings of length $n$ ending in a double zero. Then $A_1(1) = 1, A_2(1) = 1, A_3(1) = 0, A_1(2) = 2, A_2(2) = 1$ and $A_3(2) = 1$.

Note that $\mathcal{S}_n = A_1(n) + A_2(n) + A_3(n)$. For $n \geq 2$ we have $A_1(n) = \mathcal{S}_{n - 1} = A_1(n - 1) + A_2(n - 1) + A_3(n - 1)$ (since we may add a 1 to the end of any valid string of length $n - 1$ to get a valid string of length $n$), $A_2(n) = A_1(n -1)$ (since every valid string ending in 10 can be arrived at by adding a 0 to a string ending in 1) and $A_3(n) = A_2(n - 1)$ (since every valid string ending in 100 can be arrived at by adding a 0 to a string ending in 10).

Thus $\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}$. Then using the initial values $\mathcal{S}_1 = 2, \mathcal{S}_2 = 4, \mathcal{S}_3 = 7$ we can easily compute that $\mathcal{S}_{11} = 927$.


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 $n-4$. We thus have the recursion ${S}_n=2{S}_{n-1}-{S}_{n-4}$. We proceed as above.