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 "2019 AMC 10B Problems/Problem 25"
(→‎Video Solution by OmegaLearn)
 
(101 intermediate revisions by 43 users not shown)
Line 1: Line 1:
−
sub2pewds if u think this test was gg2ez
+
{{duplicate|[[2019 AMC 10B Problems#Problem 25|2019 AMC 10B #25]] and [[2019 AMC 12B Problems#Problem 23|2019 AMC 12B #23]]}}
 +
 
 +
==Problem==
 +
 
 +
How many sequences of <math>0</math>s and <math>1</math>s of length <math>19</math> are there that begin with a <math>0</math>, end with a <math>0</math>, contain no two consecutive <math>0</math>s, and contain no three consecutive <math>1</math>s?
 +
 
 +
<math>\textbf{(A) }55\qquad\textbf{(B) }60\qquad\textbf{(C) }65\qquad\textbf{(D) }70\qquad\textbf{(E) }75</math>
 +
 
 +
==Solution 1 (Recursion)==
 +
Let <math>f(n)</math> be the number of valid sequences of length <math>n</math> (satisfying the conditions given in the problem).
 +
 
 +
We know our valid sequence must end in a <math>0</math>. Then, since we cannot have two consecutive <math>0</math>s, it must end in a <math>10</math>. Now, we only have two cases: it ends with <math>010</math>, or it ends with <math>110</math> which is equivalent to <math>0110</math>. Thus, our sequence must be of the forms <math>0\ldots010</math> or <math>0\ldots0110</math>. In the first case, the first <math>n-2</math> digits are equivalent to a valid sequence of length <math>n-2</math>. In the second, the first <math>n-3</math> digits are equivalent to a valid sequence of length <math>n-3</math>. Therefore, it must be the case that <math>f(n) = f(n-3) + f(n-2)</math>, with <math>n \ge 3</math> (because otherwise, the sequence would contain only 0s and this is not allowed due to the given conditions).
 +
 
 +
It is easy to find <math>f(3) = 1</math> since the only possible valid sequence is <math>010</math>. <math>f(4)=1</math> since the only possible valid sequence is <math>0110</math>. <math>f(5)=1</math> since the only possible valid sequence is <math>01010</math>.
 +
 
 +
The recursive sequence is then as follows:
 +
 
 +
<cmath>f(3)=1</cmath>
 +
<cmath>f(4)=1</cmath>
 +
<cmath>f(5) = 1</cmath>
 +
<cmath>f(6) = 1 + 1 = 2</cmath>
 +
<cmath>f(7) = 1 + 1 = 2</cmath>
 +
<cmath>f(8) = 1 + 2 = 3</cmath>
 +
<cmath>f(9) = 2 + 2 = 4</cmath>
 +
<cmath>f(10) = 2 + 3 = 5</cmath>
 +
<cmath>f(11) = 3 + 4 = 7</cmath>
 +
<cmath>f(12) = 4 + 5 = 9</cmath>
 +
<cmath>f(13) = 5 + 7 = 12</cmath>
 +
<cmath>f(14) = 7 + 9 = 16</cmath>
 +
<cmath>f(15) = 9 + 12 = 21</cmath>
 +
<cmath>f(16) = 12 + 16 = 28</cmath>
 +
<cmath>f(17) = 16 + 21 = 37</cmath>
 +
<cmath>f(18) = 21 + 28 = 49</cmath>
 +
<cmath>f(19) = 28 + 37 = 65</cmath>
 +
 
 +
So, our answer is <math>\boxed{\text{\bf{(C)}  } 65}</math>.
 +
 
 +
 
 +
'''Contributors:'''
 +
 
 +
~Original Author
 +
 
 +
~solasky
 +
 
 +
~BakedPotato66
 +
 
 +
~[https://artofproblemsolving.com/wiki/index.php/User:Crazyvideogamez CrazyVideoGamez]
 +
 
 +
==Solution 2 (casework)==
 +
After any particular <math>0</math>, the next <math>0</math> in the sequence must appear exactly <math>2</math> or <math>3</math> positions down the line. In this case, we start at position <math>1</math> and end at position <math>19</math>, i.e. we move a total of <math>18</math> positions down the line. Therefore, we must add a series of <math>2</math>s and <math>3</math>s to get <math>18</math>. There are a number of ways to do this:
 +
 
 +
'''Case 1''': nine <math>2</math>s - there is only <math>1</math> way to arrange them.
 +
 
 +
'''Case 2''': two <math>3</math>s and six <math>2</math>s - there are <math>{8\choose2} = 28</math> ways to arrange them.
 +
 
 +
'''Case 3''': four <math>3</math>s and three <math>2</math>s - there are <math>{7\choose4} = 35</math> ways to arrange them.
 +
 
 +
'''Case 4''': six <math>3</math>s - there is only <math>1</math> way to arrange them.
 +
 
 +
Summing the four cases gives <math>1+28+35+1=\boxed{\textbf{(C) }65}</math>.
 +
 
 +
==Solution 3 (casework and blocks)==
 +
We can simplify the original problem into a problem where there are <math>2^{17}</math> binary characters with zeros at the beginning and the end. Then, we know that we cannot have a block of 2 zeroes and a block of 3 ones. Thus, our only options are a block of <math>0</math>s, <math>1</math>s, and <math>11</math>s. Now, we use casework:
 +
 
 +
'''Case 1''': Alternating 1s and 0s. There is simply 1 way to do this: <math>0101010101010101010</math>.
 +
Now, we note that there cannot be only one block of <math>11</math> in the entire sequence, as there must be zeroes at both ends and if we only include 1 block, of <math>11</math>s this cannot be satisfied. This is true for all odd numbers of <math>11</math> blocks.
 +
 
 +
'''Case 2''': There are 2 <math>11</math> blocks. Using the zeroes in the sequence as dividers, we have a sample as <math>0110110101010101010</math>. We know there are 8 places for <math>11</math>s, which will be filled by <math>1</math>s if the <math>11</math>s don't fill them. This is <math>{8\choose2} = 28</math> ways.
 +
 
 +
'''Case 3''': Four <math>11</math> blocks arranged. Using the same logic as Case 2, we have <math>{7\choose4} = 35</math> ways to arrange four <math>11</math> blocks.
 +
 
 +
'''Case 4''': No single <math>1</math> blocks, only <math>11</math> blocks. There is simply one case for this, which is <math>0110110110110110110</math>.
 +
 
 +
Adding these four cases, we have <math>1+28+35+1=\boxed{\textbf{(C) }65}</math> as our final answer.
 +
 
 +
~Equinox8
 +
 
 +
==Solution 4 (similar to #3)==
 +
Any valid sequence must start with a <math>0</math>. We can then think of constructing a sequence as adding groups of terms to this <math>0</math>, each ending in <math>0</math>. (This is always possible because every valid string ends in <math>0</math>.) For example, we can represent the string <math>01011010110110</math> as: <math>0-10-110-10-110-110</math>.
 +
To not have any consecutive 0s, we must have at least one <math>1</math> before the next <math>0</math>. However, we cannot have three or more <math>1</math>s before the next <math>0</math> because we cannot have three consecutive <math>1</math>s. Consequently, we can only have one or two <math>1</math>s.
 +
 
 +
So we can have the groups: <math>10</math> and <math>110</math>.
 +
 
 +
After the initial <math>0</math>, we have <math>18</math> digits left to fill in the string. Let the number of <math>10</math> blocks be <math>x</math>, and <math>110</math> be <math>y</math>. Then <math>x</math> and <math>y</math> must satisfy <math>2x+3y=18</math>. We recognize this as a Diophantine equation. Taking <math>\pmod{2}</math> yields <math>y=0 \pmod{2}</math>. Since <math>x</math> and <math>y</math> must both be nonnegative, we get the solutions <math>(9, 0)</math>, <math>(6, 2)</math>, <math>(3, 4)</math>, and <math>(0, 6)</math>. We now handle each of these cases separately.
 +
 
 +
<math>(9, 0)</math>: Only one arrangement, namely all <math>10</math>s.
 +
 
 +
<math>(6, 2)</math>: We have 6 groups of <math>11</math>, and <math>2</math> groups of <math>110</math>. This has <math>\binom{6+2}{2}=28</math> cases.
 +
 
 +
<math>(3, 4)</math>: This means we have 3 groups of <math>10</math>, and 4 groups of <math>110</math>. This has <math>\binom{3+4}{3}=35</math> cases.
 +
 
 +
<math>(0, 6)</math>: Only one arrangement, namely all <math>110</math>.
 +
 
 +
Adding these, we have <math>1+28+35+1=65 \longrightarrow \boxed{(C) 65}</math>.
 +
~Math4Life2020
 +
 
 +
~edited by alpha_2 for spelling and and typos
 +
 
 +
==Solution 5 (Constructive Counting)==
 +
Suppose the number of <math>0</math>s is <math>n</math>. We can construct the sequence in two steps:
 +
 
 +
Step 1: put <math>n-1</math> of <math>1</math>s between the <math>0</math>s;
 +
 
 +
Step 2: put the rest <math>19-n-(n-1)=20-2n</math> of <math>1</math>s in the <math>n-1</math> spots where there is a <math>1</math>. There are <math>\binom{n-1}{20-2n}</math> ways of doing this.
 +
 
 +
Now we find the possible values of <math>n</math>:
 +
 
 +
First of all <math>n+(n-1) \leq 19 \Rightarrow n\leq 10</math> (otherwise there will be two consecutive <math>0</math>s);
 +
 
 +
And secondly <math>20-2n \leq n-1\Rightarrow n\geq 7</math> (otherwise there will be three consecutive <math>1</math>s).
 +
 
 +
Therefore the answer is
 +
<cmath>
 +
\sum_{n=7}^{10} \binom{n-1}{20-2n} = \binom{6}{6} + \binom{7}{4} + \binom{8}{2} + \binom{9}{0} = \boxed{\textbf{(C) }65}.
 +
</cmath>
 +
 
 +
~ aops
 +
 
 +
== Solution 6 (Recursion)==
 +
 
 +
For a valid sequence of length <math>n</math>, the sequence must be in the form of <math>01xx...xx10</math>. By removing the <math>01</math> at the start of the sequence and the <math>10</math> at the end of the sequence, there are <math>n-4</math> bits left. The <math>n-4</math> bits left can be in the form of:
 +
<math>0yy...yy0</math>, the whole <math>(n-4)</math> bits are valid sequence, which is <math>f(n-4)</math>
 +
<math>0yy...y01</math>, the <math>(n-5)</math> bits before the last <math>1</math> are valid sequence, which is <math>f(n-5)</math>
 +
<math>10y...yy0</math>, the <math>(n-5)</math> bits after the first <math>1</math> are valid sequence, which is <math>f(n-5)</math>
 +
<math>10y...y01</math>, the <math>(n-6)</math> bits between the first and last <math>1</math> are valid sequence, which is <math>f(n-6)</math>
 +
 
 +
So, <math>f(n) = f(n-4) + 2f(n-5) + f(n-6)</math>
 +
 
 +
We will calculate <math>f(19)</math> by [https://en.wikipedia.org/wiki/Dynamic_programming Dynamic Programming].
 +
 
 +
<math>f(3) = 1</math>
 +
 
 +
<math>f(4) = 1</math>
 +
 
 +
<math>f(5) = 1</math>
 +
 
 +
<math>f(6) = 2</math>
 +
 
 +
<math>f(7) = 2</math>
 +
 
 +
<math>f(8) = 3</math>
 +
 
 +
<math>f(9) = f(5) + 2 \cdot f(4) + f(3) = 1 + 2 \cdot 1 + 1 = 4</math>
 +
 
 +
<math>f(10) = f(6) + 2 \cdot f(5) + f(4) = 2 + 2 \cdot 1 + 1 = 5</math>
 +
 
 +
<math>f(11) = f(7) + 2 \cdot f(6) + f(5) = 2 + 2 \cdot 1 + 1 = 7</math>
 +
 
 +
<math>f(12) = f(8) + 2 \cdot f(7) + f(6) = 3 + 2 \cdot 2 + 2 = 9</math>
 +
 
 +
<math>f(13) = f(9) + 2 \cdot f(8) + f(7) = 4 + 2 \cdot 3 + 2 = 12</math>
 +
 
 +
<math>f(14) = f(10) + 2 \cdot f(9) + f(8) = 5 + 2 \cdot 4 + 3 = 16</math>
 +
 
 +
<math>f(15) = f(11) + 2 \cdot f(10) + f(9) = 7 + 2 \cdot 5 + 4 = 21</math>
 +
 
 +
<math>f(16) = f(12) + 2 \cdot f(11) + f(10) = 9 + 2 \cdot 7 + 5 = 28</math>
 +
 
 +
<math>f(17) = f(13) + 2 \cdot f(12) + f(11) = 12 + 2 \cdot 9 + 7 = 37</math>
 +
 
 +
<math>f(18) = f(14) + 2 \cdot f(13) + f(12) = 16 + 2 \cdot 12 + 9 = 49</math>
 +
 
 +
<math>f(19) = f(15) + 2 \cdot f(14) + f(13) = 21 + 2 \cdot 16 + 12 = \boxed{\text{\bf{(C)}  } 65}</math>
 +
 
 +
We can further prove <math>f(n) = f(n-4) + 2f(n-5) + f(n-6)</math> is equivalent to <math>f(n) = f(n-2) + f(n-3)</math>
 +
 
 +
Let <math>k(n) = f(n-2) + f(n-3)</math>
 +
 
 +
<math>k(n-2) = f(n-4) + f(n-5)</math>
 +
 
 +
<math>k(n-3) = f(n-5) + f(n-6)</math>
 +
 
 +
<math>k(n-2)+ k(n-3) = f(n-4) + 2f(n-5) + f(n-6) = f(n)</math>
 +
 
 +
<math>f(n) = k(n-2)+ k(n-3)</math>
 +
 
 +
<math>f(n-2) = k(n-4)+ k(n-5)</math>
 +
 
 +
<math>f(n-3) = k(n-5)+ k(n-6)</math>
 +
 
 +
<math>k(n) = f(n-2) + f(n-3) = k(n-4)+ k(n-5) + k(n-5)+ k(n-6) = k(n-4) + 2k(n-5) + k(n-6)</math>
 +
 
 +
So <math>k(n)</math> is the same as <math>f(n)</math>.
 +
 
 +
~[https://artofproblemsolving.com/wiki/index.php/User:Isabelchen isabelchen]
 +
 
 +
== Solution 7 (Quick Solution by Estimating) ==
 +
 
 +
Using the tree diagram, you quickly notice that your answer must be very close to a power of <math>2</math> due to the splitting of the tree branches in a tree diagram. <math>2^6</math> is <math>64</math>, which is very close to <math>65</math>, thus giving our answer of <math>\boxed{\textbf{(C) }65}</math>.
 +
 
 +
~MichaeLLin16 ~Minor Edit and Moving by [https://artofproblemsolving.com/wiki/index.php/User:HappySharks HappySharks]
 +
 
 +
 
 +
== Solution 8 (Sequence Dividing and Path Counting) ==
 +
 
 +
You can split the sequence into <math>0</math> and <math>6</math> strings of three numbers, which can only be <math>010</math>,<math>011</math>,<math>110</math>,<math>101</math>, labelled as A,B,C,D respectively. For example, <math>0101....010</math> is labelled <math>0DADADA</math>. This can also be stated as 0, <math>D_{1}, A_{2}, D_{3},</math> etc. The problem is equivalent to find the number of such sequences. For each string, A can be followed by C and D, B can be followed by A and B, C can be followed by C and D, D can be followed by A,B, and D.  If we define <math>n(A_{i})</math> as number of possible sequences that ends with string A at the <math>i</math>th spot (thus be <math>3i+1</math> numbers long), we may find relationship between these numbers by noting that, for the <math>i+1</math> th string, with <math>i \geq 1</math>
 +
<math>n(A_{i+1}) = n(B_{i+1}) = n(B_{i}) + n(D_{i}), n(C_{i+1}) = n(A_{i}) + n(C_{i})</math>
 +
<math>n(D_{i+1}) =  n(A_{i}) + n(C_{i}) + n(D_{i})</math>.
 +
Since the first number of the sequence must be zero, we must start with <math>n(A_1) = n(B_1) = 0, n(C_1) = n(D_1) = 1</math>. Using the above steps to evolve the situation from i = 1 to i = 6, we get <math>n(A_{6}) = 37, n(B_{6}) = 37, n(C_{6}) = 28, n(D_{6}) = 49</math>.
 +
Since the sequence ends with 0, we only need to sum <math>n(A_{6})</math> and <math>n(C_{6})</math>, which yields <math>37+28=65</math>.  <math>\boxed{\textbf{(C) }65}</math>
 +
 
 +
Solution by ~Cc2010cc2015
 +
 
 +
minor edit by ~CLA
 +
 
 +
== Video Solution by OmegaLearn ==
 +
https://youtu.be/WpSpnx8PPnc?t=94
 +
 
 +
~pi_is_3.14
 +
 
 +
==Video Solution==
 +
https://youtu.be/VamT49PjmdI
 +
 
 +
==See Also==
 +
{{AMC10 box|year=2019|ab=B|num-b=24|after=Last Problem}}
 +
{{AMC12 box|year=2019|ab=B|num-b=22|num-a=24}}
 +
{{MAA Notice}}
 +
 
 +
[[Category: Intermediate Combinatorics Problems]]

Latest revision as of 19:00, 14 November 2024

The following problem is from both the 2019 AMC 10B #25 and 2019 AMC 12B #23, so both problems redirect to this page.

Problem

How many sequences of $0$s and $1$s of length $19$ are there that begin with a $0$, end with a $0$, contain no two consecutive $0$s, and contain no three consecutive $1$s?

$\textbf{(A) }55\qquad\textbf{(B) }60\qquad\textbf{(C) }65\qquad\textbf{(D) }70\qquad\textbf{(E) }75$

Solution 1 (Recursion)

Let $f(n)$ be the number of valid sequences of length $n$ (satisfying the conditions given in the problem).

We know our valid sequence must end in a $0$. Then, since we cannot have two consecutive $0$s, it must end in a $10$. Now, we only have two cases: it ends with $010$, or it ends with $110$ which is equivalent to $0110$. Thus, our sequence must be of the forms $0\ldots010$ or $0\ldots0110$. In the first case, the first $n-2$ digits are equivalent to a valid sequence of length $n-2$. In the second, the first $n-3$ digits are equivalent to a valid sequence of length $n-3$. Therefore, it must be the case that $f(n) = f(n-3) + f(n-2)$, with $n \ge 3$ (because otherwise, the sequence would contain only 0s and this is not allowed due to the given conditions).

It is easy to find $f(3) = 1$ since the only possible valid sequence is $010$. $f(4)=1$ since the only possible valid sequence is $0110$. $f(5)=1$ since the only possible valid sequence is $01010$.

The recursive sequence is then as follows:

\[f(3)=1\] \[f(4)=1\] \[f(5) = 1\] \[f(6) = 1 + 1 = 2\] \[f(7) = 1 + 1 = 2\] \[f(8) = 1 + 2 = 3\] \[f(9) = 2 + 2 = 4\] \[f(10) = 2 + 3 = 5\] \[f(11) = 3 + 4 = 7\] \[f(12) = 4 + 5 = 9\] \[f(13) = 5 + 7 = 12\] \[f(14) = 7 + 9 = 16\] \[f(15) = 9 + 12 = 21\] \[f(16) = 12 + 16 = 28\] \[f(17) = 16 + 21 = 37\] \[f(18) = 21 + 28 = 49\] \[f(19) = 28 + 37 = 65\]

So, our answer is $\boxed{\text{\bf{(C)} } 65}$.


Contributors:

~Original Author

~solasky

~BakedPotato66

~CrazyVideoGamez

Solution 2 (casework)

After any particular $0$, the next $0$ in the sequence must appear exactly $2$ or $3$ positions down the line. In this case, we start at position $1$ and end at position $19$, i.e. we move a total of $18$ positions down the line. Therefore, we must add a series of $2$s and $3$s to get $18$. There are a number of ways to do this:

Case 1: nine $2$s - there is only $1$ way to arrange them.

Case 2: two $3$s and six $2$s - there are ${8\choose2} = 28$ ways to arrange them.

Case 3: four $3$s and three $2$s - there are ${7\choose4} = 35$ ways to arrange them.

Case 4: six $3$s - there is only $1$ way to arrange them.

Summing the four cases gives $1+28+35+1=\boxed{\textbf{(C) }65}$.

Solution 3 (casework and blocks)

We can simplify the original problem into a problem where there are $2^{17}$ binary characters with zeros at the beginning and the end. Then, we know that we cannot have a block of 2 zeroes and a block of 3 ones. Thus, our only options are a block of $0$s, $1$s, and $11$s. Now, we use casework:

Case 1: Alternating 1s and 0s. There is simply 1 way to do this: $0101010101010101010$. Now, we note that there cannot be only one block of $11$ in the entire sequence, as there must be zeroes at both ends and if we only include 1 block, of $11$s this cannot be satisfied. This is true for all odd numbers of $11$ blocks.

Case 2: There are 2 $11$ blocks. Using the zeroes in the sequence as dividers, we have a sample as $0110110101010101010$. We know there are 8 places for $11$s, which will be filled by $1$s if the $11$s don't fill them. This is ${8\choose2} = 28$ ways.

Case 3: Four $11$ blocks arranged. Using the same logic as Case 2, we have ${7\choose4} = 35$ ways to arrange four $11$ blocks.

Case 4: No single $1$ blocks, only $11$ blocks. There is simply one case for this, which is $0110110110110110110$.

Adding these four cases, we have $1+28+35+1=\boxed{\textbf{(C) }65}$ as our final answer.

~Equinox8

Solution 4 (similar to #3)

Any valid sequence must start with a $0$. We can then think of constructing a sequence as adding groups of terms to this $0$, each ending in $0$. (This is always possible because every valid string ends in $0$.) For example, we can represent the string $01011010110110$ as: $0-10-110-10-110-110$. To not have any consecutive 0s, we must have at least one $1$ before the next $0$. However, we cannot have three or more $1$s before the next $0$ because we cannot have three consecutive $1$s. Consequently, we can only have one or two $1$s.

So we can have the groups: $10$ and $110$.

After the initial $0$, we have $18$ digits left to fill in the string. Let the number of $10$ blocks be $x$, and $110$ be $y$. Then $x$ and $y$ must satisfy $2x+3y=18$. We recognize this as a Diophantine equation. Taking $\pmod{2}$ yields $y=0 \pmod{2}$. Since $x$ and $y$ must both be nonnegative, we get the solutions $(9, 0)$, $(6, 2)$, $(3, 4)$, and $(0, 6)$. We now handle each of these cases separately.

$(9, 0)$: Only one arrangement, namely all $10$s.

$(6, 2)$: We have 6 groups of $11$, and $2$ groups of $110$. This has $\binom{6+2}{2}=28$ cases.

$(3, 4)$: This means we have 3 groups of $10$, and 4 groups of $110$. This has $\binom{3+4}{3}=35$ cases.

$(0, 6)$: Only one arrangement, namely all $110$.

Adding these, we have $1+28+35+1=65 \longrightarrow \boxed{(C) 65}$. ~Math4Life2020

~edited by alpha_2 for spelling and and typos

Solution 5 (Constructive Counting)

Suppose the number of $0$s is $n$. We can construct the sequence in two steps:

Step 1: put $n-1$ of $1$s between the $0$s;

Step 2: put the rest $19-n-(n-1)=20-2n$ of $1$s in the $n-1$ spots where there is a $1$. There are $\binom{n-1}{20-2n}$ ways of doing this.

Now we find the possible values of $n$:

First of all $n+(n-1) \leq 19 \Rightarrow n\leq 10$ (otherwise there will be two consecutive $0$s);

And secondly $20-2n \leq n-1\Rightarrow n\geq 7$ (otherwise there will be three consecutive $1$s).

Therefore the answer is \[\sum_{n=7}^{10} \binom{n-1}{20-2n} = \binom{6}{6} + \binom{7}{4} + \binom{8}{2} + \binom{9}{0} = \boxed{\textbf{(C) }65}.\]

~ aops

Solution 6 (Recursion)

For a valid sequence of length $n$, the sequence must be in the form of $01xx...xx10$. By removing the $01$ at the start of the sequence and the $10$ at the end of the sequence, there are $n-4$ bits left. The $n-4$ bits left can be in the form of: 

$0yy...yy0$, the whole $(n-4)$ bits are valid sequence, which is $f(n-4)$
$0yy...y01$, the $(n-5)$ bits before the last $1$ are valid sequence, which is $f(n-5)$
$10y...yy0$, the $(n-5)$ bits after the first $1$ are valid sequence, which is $f(n-5)$
$10y...y01$, the $(n-6)$ bits between the first and last $1$ are valid sequence, which is $f(n-6)$

So, $f(n) = f(n-4) + 2f(n-5) + f(n-6)$

We will calculate $f(19)$ by Dynamic Programming.

$f(3) = 1$

$f(4) = 1$

$f(5) = 1$

$f(6) = 2$

$f(7) = 2$

$f(8) = 3$

$f(9) = f(5) + 2 \cdot f(4) + f(3) = 1 + 2 \cdot 1 + 1 = 4$

$f(10) = f(6) + 2 \cdot f(5) + f(4) = 2 + 2 \cdot 1 + 1 = 5$

$f(11) = f(7) + 2 \cdot f(6) + f(5) = 2 + 2 \cdot 1 + 1 = 7$

$f(12) = f(8) + 2 \cdot f(7) + f(6) = 3 + 2 \cdot 2 + 2 = 9$

$f(13) = f(9) + 2 \cdot f(8) + f(7) = 4 + 2 \cdot 3 + 2 = 12$

$f(14) = f(10) + 2 \cdot f(9) + f(8) = 5 + 2 \cdot 4 + 3 = 16$

$f(15) = f(11) + 2 \cdot f(10) + f(9) = 7 + 2 \cdot 5 + 4 = 21$

$f(16) = f(12) + 2 \cdot f(11) + f(10) = 9 + 2 \cdot 7 + 5 = 28$

$f(17) = f(13) + 2 \cdot f(12) + f(11) = 12 + 2 \cdot 9 + 7 = 37$

$f(18) = f(14) + 2 \cdot f(13) + f(12) = 16 + 2 \cdot 12 + 9 = 49$

$f(19) = f(15) + 2 \cdot f(14) + f(13) = 21 + 2 \cdot 16 + 12 = \boxed{\text{\bf{(C)} } 65}$

We can further prove $f(n) = f(n-4) + 2f(n-5) + f(n-6)$ is equivalent to $f(n) = f(n-2) + f(n-3)$

Let $k(n) = f(n-2) + f(n-3)$

$k(n-2) = f(n-4) + f(n-5)$

$k(n-3) = f(n-5) + f(n-6)$

$k(n-2)+ k(n-3) = f(n-4) + 2f(n-5) + f(n-6) = f(n)$

$f(n) = k(n-2)+ k(n-3)$

$f(n-2) = k(n-4)+ k(n-5)$

$f(n-3) = k(n-5)+ k(n-6)$

$k(n) = f(n-2) + f(n-3) = k(n-4)+ k(n-5) + k(n-5)+ k(n-6) = k(n-4) + 2k(n-5) + k(n-6)$

So $k(n)$ is the same as $f(n)$.

~isabelchen

Solution 7 (Quick Solution by Estimating)

Using the tree diagram, you quickly notice that your answer must be very close to a power of $2$ due to the splitting of the tree branches in a tree diagram. $2^6$ is $64$, which is very close to $65$, thus giving our answer of $\boxed{\textbf{(C) }65}$.

~MichaeLLin16 ~Minor Edit and Moving by HappySharks


Solution 8 (Sequence Dividing and Path Counting)

You can split the sequence into $0$ and $6$ strings of three numbers, which can only be $010$,$011$,$110$,$101$, labelled as A,B,C,D respectively. For example, $0101....010$ is labelled $0DADADA$. This can also be stated as 0, $D_{1}, A_{2}, D_{3},$ etc. The problem is equivalent to find the number of such sequences. For each string, A can be followed by C and D, B can be followed by A and B, C can be followed by C and D, D can be followed by A,B, and D. If we define $n(A_{i})$ as number of possible sequences that ends with string A at the $i$th spot (thus be $3i+1$ numbers long), we may find relationship between these numbers by noting that, for the $i+1$ th string, with $i \geq 1$ 

$n(A_{i+1}) = n(B_{i+1}) = n(B_{i}) + n(D_{i}), n(C_{i+1}) = n(A_{i}) + n(C_{i})$ 
$n(D_{i+1}) =  n(A_{i}) + n(C_{i}) + n(D_{i})$.

Since the first number of the sequence must be zero, we must start with $n(A_1) = n(B_1) = 0, n(C_1) = n(D_1) = 1$. Using the above steps to evolve the situation from i = 1 to i = 6, we get $n(A_{6}) = 37, n(B_{6}) = 37, n(C_{6}) = 28, n(D_{6}) = 49$. Since the sequence ends with 0, we only need to sum $n(A_{6})$ and $n(C_{6})$, which yields $37+28=65$. $\boxed{\textbf{(C) }65}$

Solution by ~Cc2010cc2015

minor edit by ~CLA

Video Solution by OmegaLearn

https://youtu.be/WpSpnx8PPnc?t=94

~pi_is_3.14

Video Solution

https://youtu.be/VamT49PjmdI

See Also

2019 AMC 10B (Problems • Answer Key • Resources)
Preceded by
Problem 24 		Followed by
Last Problem
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 10 Problems and Solutions
2019 AMC 12B (Problems • Answer Key • Resources)
Preceded by
Problem 22 		Followed by
Problem 24
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 12 Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2019_AMC_10B_Problems/Problem_25&oldid=234175"