Difference between revisions of "2019 AMC 10B Problems/Problem 25"

(Solution 1 (recursion))
m (Solution 1 (recursion))
(10 intermediate revisions by 5 users not shown)
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>.
 
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>.
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>.
+
Let <math>f(n)</math> be the number of valid (meaning: the sequence contains 0s and 1s, starts and ends with both 0, and there are no two consecutive 0s and no three consecutive 1s) 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.
+
Then we can define a recursive function <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 give conditions).  
  
It is easy to find <math>f(5) = 1</math> with the only possible sequence being <math>01010</math> and <math>f(6) = 2</math> with the only two possible sequences being <math>011010</math> and <math>010110</math> by hand, and then by the recursive formula, we have <math>f(19) = \boxed{\textbf{(C) }65}</math>.
+
We derived the recursive function, since for any valid sequence of length <math>n</math>, you can append either <math>10</math> or <math>110</math> to return to the starting position, 0, and the resulting sequence will still satisfy 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
  
 
==Solution 2 (casework)==
 
==Solution 2 (casework)==
Line 27: 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 (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 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 3 or more 1s before the next 0 because we cannot have 3 consecutive 1s. Consequently, we can only have one or two 1s. So we can have the groups:
 +
10, 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 <math>2x+3y=18</math>. We recognize this as a Diophantine equation. Taking <math>(mod 2)</math> yields <math>y=0 (mod 2)</math>. Since x and y must both be nonnegative, we get the solutions (9, 0); (6, 2); (3, 4); (0, 6). We now handle each of these cases separately.
 +
 +
(9, 0): Only one arrangement, namely all "01".
 +
 +
(6, 2): Of the 8, we choose 2 to be "001". This has 8C2=28 cases.
 +
 +
(3, 4): Of the 7, we choose 4 to be "001". This has 7C3=35 cases.
 +
 +
(0, 6): Only one arrangement, namely all "001".
 +
 +
Adding these, we have <math>1+28+35+1=65 \longrightarrow \boxed{(C)}</math>.
 +
~Math4Life2020
  
 
==Video Solution==
 
==Video Solution==

Revision as of 20:09, 27 April 2021

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)

We can deduce, from the given restrictions, that any valid sequence of length $n$ will start with a $0$ followed by either $10$ or $110$. Let $f(n)$ be the number of valid (meaning: the sequence contains 0s and 1s, starts and ends with both 0, and there are no two consecutive 0s and no three consecutive 1s) sequences of length $n$.

Then we can define a recursive function $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 give conditions).

We derived the recursive function, since for any valid sequence of length $n$, you can append either $10$ or $110$ to return to the starting position, 0, and the resulting sequence will still satisfy 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

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 3 or more 1s before the next 0 because we cannot have 3 consecutive 1s. Consequently, we can only have one or two 1s. So we can have the groups: 10, 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 $(mod 2)$ yields $y=0 (mod 2)$. Since x and y must both be nonnegative, we get the solutions (9, 0); (6, 2); (3, 4); (0, 6). We now handle each of these cases separately.

(9, 0): Only one arrangement, namely all "01".

(6, 2): Of the 8, we choose 2 to be "001". This has 8C2=28 cases.

(3, 4): Of the 7, we choose 4 to be "001". This has 7C3=35 cases.

(0, 6): Only one arrangement, namely all "001".

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

Video Solution

For those who want a video solution: https://youtu.be/VamT49PjmdI

See Also

2019 AMC 10B (ProblemsAnswer KeyResources)
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 (ProblemsAnswer KeyResources)
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