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))
(removed solution 3 - the same as solution 1, just less formal)
Line 27: Line 27:
  
 
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)==
 
−
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.
 
−
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.
 
−
Continue this process until 19 and you get  <math> \boxed{\textbf{(C) }65}</math>.
 
  
 
==Video Solution==
 
==Video Solution==
Line 41: Line 35:
 
{{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
 

Revision as of 14:06, 28 February 2019

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$ and $f(6) = 2$ 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\choose3} = 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}$.

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=103942"