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"

(→‎Solution 3(Simpler))
(→‎Video Solution by OmegaLearn)
 
(59 intermediate revisions by 26 users not shown)
Line 1: Line 1:
−
{{duplicate|[[2019 AMC 10B Problems|2019 AMC 10B #25]] and [[2019 AMC 12B Problems|2019 AMC 12B #23]]}}
+
{{duplicate|[[2019 AMC 10B Problems#Problem 25|2019 AMC 10B #25]] and [[2019 AMC 12B Problems#Problem 23|2019 AMC 12B #23]]}}
  
 
==Problem==
 
==Problem==
Line 7: Line 7:
 
<math>\textbf{(A) }55\qquad\textbf{(B) }60\qquad\textbf{(C) }65\qquad\textbf{(D) }70\qquad\textbf{(E) }75</math>
 
<math>\textbf{(A) }55\qquad\textbf{(B) }60\qquad\textbf{(C) }65\qquad\textbf{(D) }70\qquad\textbf{(E) }75</math>
  
−
==Solution 1 (recursion)==
+
==Solution 1 (Recursion)==
−
We can deduce, from the given restrictions, that any valid sequence of length <math>n</math> will start with a <math>0</math> followed by either <math>10</math> or <math>110</math>.
+
Let <math>f(n)</math> be the number of valid sequences of length <math>n</math> (satisfying the conditions given in the problem).  
−
Thus we can define a recursive function <math>f(n) = f(n-3) + f(n-2)</math>, where <math>f(n)</math> is the number of valid sequences of length <math>n</math>.
 
  
−
This is because for any valid sequence of length <math>n</math>, you can append either <math>10</math> or <math>110</math> and the resulting sequence will still satisfy the given conditions.
+
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(5) = 1</math> and <math>f(6) = 2</math> by hand, and then by the recursive formula, we have <math>f(19) = \boxed{\textbf{(C) }65}</math>.
+
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)==
 
==Solution 2 (casework)==
Line 22: Line 54:
 
'''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 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\choose3} = 35</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.
 
'''Case 4''': six <math>3</math>s - there is only <math>1</math> way to arrange them.
Line 28: Line 60:
 
Summing the four cases gives <math>1+28+35+1=\boxed{\textbf{(C) }65}</math>.
 
Summing the four cases gives <math>1+28+35+1=\boxed{\textbf{(C) }65}</math>.
  
−
==Solution 3(Simpler)==
+
==Solution 3 (casework and blocks)==
−
Firstly, notice how the ending of a suitable string could be a 010, or a 0110. This information basically gives us the answer, as we know that for any string of length N, the possible solutions, would be a string of length n-2, with 10 appended, and a string of length n-3, with 110 appended.  
+
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:
−
For example:
+
 
−
The strings of length 4 are 0110, the strings of length 5 are 01010, so to make length 7 we can add a 10 to length 5, 0101010, and then add 110 to the string of length 4, 0110110, these are the only possible strings, since the endings have to be 10, or 110, and the strings of length 5 and 4, work and can be modified to work as a 7, since they end with 0.  
+
'''Case 1''': Alternating 1s and 0s. There is simply 1 way to do this: <math>0101010101010101010</math>.
−
Continue this process until 19 and you get  <math> \boxed{\textbf{(C) }65}</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==
 
==Video Solution==
−
For those who want a video solution: https://youtu.be/VamT49PjmdI
+
https://youtu.be/VamT49PjmdI
  
 
==See Also==
 
==See Also==
Line 41: Line 216:
 
{{AMC12 box|year=2019|ab=B|num-b=22|num-a=24}}
 
{{AMC12 box|year=2019|ab=B|num-b=22|num-a=24}}
 
{{MAA Notice}}
 
{{MAA Notice}}
−
SUB2PEWDS
+
 
 +
[[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"