2019 AMC 10B Problems/Problem 25
- The following problem is from both the 2019 AMC 10B #25 and 2019 AMC 12B #23, so both problems redirect to this page.
Contents
Problem
How many sequences of s and
s of length
are there that begin with a
, end with a
, contain no two consecutive
s, and contain no three consecutive
s?
Solution 1 (recursion)
We can deduce, from the given restrictions, that any valid sequence of length will start with a
followed by either
or
.
Thus we can define a recursive function
, where
is the number of valid sequences of length
.
This is because for any valid sequence of length , you can append either
or
and the resulting sequence will still satisfy the given conditions.
It is easy to find and
by hand, and then by the recursive formula, we have
.
Solution 2 (casework)
After any particular , the next
in the sequence must appear exactly
or
positions down the line. In this case, we start at position
and end at position
, i.e. we move a total of
positions down the line. Therefore, we must add a series of
s and
s to get
. There are a number of ways to do this:
Case 1: nine s - there is only
way to arrange them.
Case 2: two s and six
s - there are
ways to arrange them.
Case 3: four s and three
s - there are
ways to arrange them.
Case 4: six s - there is only
way to arrange them.
Summing the four cases gives .
Solution 3(manual counting)
We construct a tree starting with 0, going down to 1, and going down with all other allowed numbers, for a 1 after a 0, we split off into two branches of 1 and 0, and we follow anything else logically. We then chose all of the strings ending with 1 then 0, of lengths 4 to 12. (constructing a tree speeds this up) Here they are:
4 : 1
5 : 1
6 : 2
7 : 2
8 : 3
9 : 4
10 : 4
11 : 7
12 : 7
Notice how every two terms are the same and they form a Fibonacci sequence. Continuing this Fibonacci, every two terms until 19 you get .
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.
SUB2PEWDS