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

m (Solution 2 (Casework))
m (Solution 2 (Casework))
Line 20: Line 20:
 
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?
 
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).
+
Option 1: Nine 2's (there is only 1 way to arrange this).
  
Option 2: two 3's and six 2's (<math>{8\choose2} =28</math> ways to arrange this).
+
Option 2: Two 3's and six 2's (<math>{8\choose2} =28</math> ways to arrange this).
  
Option 3: four 3's and three 2's (<math>{7\choose3}=35</math> ways to arrange this).
+
Option 3: Four 3's and three 2's (<math>{7\choose3}=35</math> ways to arrange this).
  
Option 4: six 3's (there is only 1 way to arrange this).
+
Option 4: Six 3's (there is only 1 way to arrange this).
  
Sum the four numbers given above: 1+28+35+1=65
+
Sum the four numbers given above: <math>1+28+35+1=\boxed{65}</math>
  
 
Solution by: mxnxn
 
Solution by: mxnxn

Revision as of 14:50, 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 that any valid sequence of length $n$ will start with a 0 followed by either "10" or "110". Because of this, we can define a recursive function:

$f(n) = f(n-3) + f(n-2)$

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

$f(5) = 1$ and $f(6) = 2$, so you follow the recursion up until $f(19) = 65 \quad \boxed{C}$

Solution 2 (Casework)

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).

Option 2: Two 3's and six 2's (${8\choose2} =28$ ways to arrange this).

Option 3: Four 3's and three 2's (${7\choose3}=35$ ways to arrange this).

Option 4: Six 3's (there is only 1 way to arrange this).

Sum the four numbers given above: $1+28+35+1=\boxed{65}$

Solution by: mxnxn

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