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"

(Added Solution 3)
m (→‎Solution 3 (casework and blocks))
Line 30: Line 30:
 
==Solution 3 (casework and blocks)==
 
==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:  
 
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>.  
 
'''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.  
 
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 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 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>.  
 
'''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>.  
  

Revision as of 20:02, 7 May 2020

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$. Thus we can define a recursive function $f(n) = f(n-3) + f(n-2)$, where $f(n)$ is the number of valid sequences of length $n$.

This is because for any valid sequence of length $n$, you can append either $10$ or $110$ and the resulting sequence will still satisfy the given conditions.

It is easy to find $f(5) = 1$ with the only possible sequence being $01010$ and $f(6) = 2$ with the only two possible sequences being $011010$ and $010110$ by hand, and then by the recursive formula, we have $f(19) = \boxed{\textbf{(C) }65}$.

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

Video Solution

For those who want a 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=122159"