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

Revision as of 23:07, 17 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

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.

@@ 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>
-==Solution 1 (Recursion)==
+==Solution 1 (recursion)==
-We can deduce that any valid sequence of length <math>n</math> will start with a 0 followed by either "10" or "110".
+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>.
-Because of this, we can define a recursive function:
+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>.
-<math>f(n) = f(n-3) + f(n-2)</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.
-This is because for any valid sequence of length <math>n</math>, you can append either "10" or "110" and the resulting sequence would 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>.
-<math>f(5) = 1</math> and <math>f(6) = 2</math>, so you follow the recursion up until <math>f(19) = 65 \quad \boxed{C}</math>
+==Solution 2 (casework)==
+After any particular <math>0</math>, the next <math>0</math> in the sequence must appear exactly <math>2</math> or <math>3</math> positions down the line. In this case, we start at position <math>1</math> and end at position <math>19</math>, i.e. we move a total of <math>18</math> positions down the line. Therefore, we must add a series of <math>2</math>s and <math>3</math>s to get <math>18</math>. There are a number of ways to do this:
-==Solution 2 (Casework)==
+'''Case 1''': nine <math>2</math>s - there is only <math>1</math> way to arrange them.
-After any given zero, the next zero must appear exactly two or three spots down the line. And we started at position 1 and ended at position 19, so we moved over 18. Therefore, we must add a series of 2's and 3's to get 18. How can we do this?
-Option 1: Nine 2's (there is only 1 way to arrange this).
+'''Case 2''': two <math>3</math>s and six <math>2</math>s - there are <math>{8\choose2} = 28</math> ways to arrange them.
-Option 2: Two 3's and six 2's (<math>{8\choose2} =28</math> ways to arrange this).
+'''Case 3''': four <math>3</math>s and three <math>2</math>s - there are <math>{7\choose3} = 35</math> ways to arrange them.
-Option 3: Four 3's and three 2's (<math>{7\choose3}=35</math> ways to arrange this).
+'''Case 4''': six <math>3</math>s - there is only <math>1</math> way to arrange them.
-Option 4: Six 3's (there is only 1 way to arrange this).
+Summing the four cases gives <math>1+28+35+1=\boxed{\textbf{(C) }65}</math>.
-Sum the four numbers given above: <math>1+28+35+1=\boxed{65}</math>
-Solution by: mxnxn
 ==Video Solution==
 For those who want a video solution: https://youtu.be/VamT49PjmdI
 ==See Also==
 {{AMC10 box|year=2019|ab=B|num-b=24|after=Last Problem}}
 {{AMC12 box|year=2019|ab=B|num-b=22|num-a=24}}
 {{MAA Notice}}

Page

Toolbox

Search