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

(Fixed some formatting and LaTeX issues, and generally improved clarity and readability of the solutions)
(Solution 1 (recursion))
(6 intermediate revisions by 4 users not shown)
Line 13: Line 13:
 
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.
 
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.
  
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(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>.
  
 
==Solution 2 (casework)==
 
==Solution 2 (casework)==
Line 22: Line 22:
 
'''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.

Revision as of 17:18, 12 January 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}$.

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