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

m (Solution)
m (Solution 2)
Line 19: Line 19:
 
~Solution by MagentaCobra
 
~Solution by MagentaCobra
  
==Solution 2==
+
==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?
 
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?
  

Revision as of 17:20, 14 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

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 by MagentaCobra

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=65 ~Solution by mxnxn

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

Invalid username
Login to AoPS