Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

m
(→‎Solution)
Line 2: Line 2:
 
Let <math>\mathcal{S}_{n}</math> be the set of strings with only 0's or 1's with length <math>n</math> such that any 3 adjacent place numbers sum to at least 1. For example, <math>00100</math> works, but <math>10001</math> does not. Find the number of elements in <math>\mathcal{S}_{11}</math>.
 
Let <math>\mathcal{S}_{n}</math> be the set of strings with only 0's or 1's with length <math>n</math> such that any 3 adjacent place numbers sum to at least 1. For example, <math>00100</math> works, but <math>10001</math> does not. Find the number of elements in <math>\mathcal{S}_{11}</math>.
 
==Solution==
 
==Solution==
−
{{solution}}
+
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>S_n = A_1(n) + A_2(n) + A_3(n)</math>.  For <math>n \geq 2</math> we have <math>A_1(n) = 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>S_n = A_1(n) + A_2(n) + A_3(n) = S_{n - 1} + A_1(n - 1) + A_2(n - 1) = S_{n -1} + S_{n - 2} + A_1(n - 2) = S_{n - 1} + S_{n -2} + S_{n - 3}</math>.  Then using the initial values <math>S_1 = 1, S_2 = 2, S_3 = 4</math> we can easily compute that <math>S_11 = 504</math>.
 
----
 
----
  

Revision as of 17:04, 23 August 2006

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

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 $S_n = A_1(n) + A_2(n) + A_3(n)$. For $n \geq 2$ we have $A_1(n) = 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 $S_n = A_1(n) + A_2(n) + A_3(n) = S_{n - 1} + A_1(n - 1) + A_2(n - 1) = S_{n -1} + S_{n - 2} + A_1(n - 2) = S_{n - 1} + S_{n -2} + S_{n - 3}$. Then using the initial values $S_1 = 1, S_2 = 2, S_3 = 4$ we can easily compute that $S_11 = 504$.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_1_2006-2007_Problems/Problem_11&oldid=9847"