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.
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 .
For those who want a video solution: https://youtu.be/VamT49PjmdI
|2019 AMC 10B (Problems • Answer Key • Resources)|
|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)|
|All AMC 12 Problems and Solutions|