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
- 1 Problem
- 2 Solution 1 (Recursion)
- 3 Solution 2 (casework)
- 4 Solution 3 (casework and blocks)
- 5 Solution 4 (similar to #3)
- 6 Solution 5 (Constructive Counting)
- 7 Solution 6 (Recursion)
- 8 Solution 7 (Quick Solution by Estimating)
- 9 Solution 8 (Sequence Dividing and Path Counting)
- 10 Video Solution by OmegaLearn
- 11 Video Solution
- 12 See Also
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)
Let be the number of valid sequences of length
(satisfying the conditions given in the problem).
We know our valid sequence must end in a . Then, since we cannot have two consecutive
s, it must end in a
. Now, we only have two cases: it ends with
, or it ends with
which is equivalent to
. Thus, our sequence must be of the forms
or
. In the first case, the first
digits are equivalent to a valid sequence of length
. In the second, the first
digits are equivalent to a valid sequence of length
. Therefore, it must be the case that
, with
(because otherwise, the sequence would contain only 0s and this is not allowed due to the given conditions).
It is easy to find since the only possible valid sequence is
.
since the only possible valid sequence is
.
since the only possible valid sequence is
.
The recursive sequence is then as follows:
So, our answer is .
Contributors:
~Original Author
~solasky
~BakedPotato66
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 (casework and blocks)
We can simplify the original problem into a problem where there are binary characters with zeros at the beginning and the end. Then, we know that we cannot have a block of 2 zeroes and a block of 3 ones. Thus, our only options are a block of
s,
s, and
s. Now, we use casework:
Case 1: Alternating 1s and 0s. There is simply 1 way to do this: .
Now, we note that there cannot be only one block of
in the entire sequence, as there must be zeroes at both ends and if we only include 1 block, of
s this cannot be satisfied. This is true for all odd numbers of
blocks.
Case 2: There are 2 blocks. Using the zeroes in the sequence as dividers, we have a sample as
. We know there are 8 places for
s, which will be filled by
s if the
s don't fill them. This is
ways.
Case 3: Four blocks arranged. Using the same logic as Case 2, we have
ways to arrange four
blocks.
Case 4: No single blocks, only
blocks. There is simply one case for this, which is
.
Adding these four cases, we have as our final answer.
~Equinox8
Solution 4 (similar to #3)
Any valid sequence must start with a . We can then think of constructing a sequence as adding groups of terms to this
, each ending in
. (This is always possible because every valid string ends in
.) For example, we can represent the string
as:
.
To not have any consecutive 0s, we must have at least one
before the next
. However, we cannot have three or more
s before the next
because we cannot have three consecutive
s. Consequently, we can only have one or two
s.
So we can have the groups: and
.
After the initial , we have
digits left to fill in the string. Let the number of
blocks be
, and
be
. Then
and
must satisfy
. We recognize this as a Diophantine equation. Taking
yields
. Since
and
must both be nonnegative, we get the solutions
,
,
, and
. We now handle each of these cases separately.
: Only one arrangement, namely all
s.
: We have 6 groups of
, and
groups of
. This has
cases.
: This means we have 3 groups of
, and 4 groups of
. This has
cases.
: Only one arrangement, namely all
.
Adding these, we have .
~Math4Life2020
~edited by alpha_2 for spelling and and typos
Solution 5 (Constructive Counting)
Suppose the number of s is
. We can construct the sequence in two steps:
Step 1: put of
s between the
s;
Step 2: put the rest of
s in the
spots where there is a
. There are
ways of doing this.
Now we find the possible values of :
First of all (otherwise there will be two consecutive
s);
And secondly (otherwise there will be three consecutive
s).
Therefore the answer is
~ aops
Solution 6 (Recursion)
For a valid sequence of length , the sequence must be in the form of
. By removing the
at the start of the sequence and the
at the end of the sequence, there are
bits left. The
bits left can be in the form of:
, the whole
bits are valid sequence, which is
![]()
, the
bits before the last
are valid sequence, which is
![]()
, the
bits after the first
are valid sequence, which is
![]()
, the
bits between the first and last
are valid sequence, which is
![]()
So,
We will calculate by Dynamic Programming.
We can further prove is equivalent to
Let
So is the same as
.
Solution 7 (Quick Solution by Estimating)
Using the tree diagram, you quickly notice that your answer must be very close to a power of due to the splitting of the tree branches in a tree diagram.
is
, which is very close to
, thus giving our answer of
.
~MichaeLLin16 ~Minor Edit and Moving by HappySharks
Solution 8 (Sequence Dividing and Path Counting)
You can split the sequence into and
strings of three numbers, which can only be
,
,
,
, labelled as A,B,C,D respectively. For example,
is labelled
. The problem is equivalent to find the number of such sequence.
For the (i+1)th string, A_{i+1} = C_{i+1} = B_{i} + D_{i}, C_{i+1} = A_{i} + C_{i}, D_{i+1} = A_{i} + C_{i} + D_{i}.
A_1 = B_1 = 0, C_1 = D_1 = 1; Repeat this step for i = 1 to 6, we get A_{6} = 37, B_{6} = 37, C_{6} = 28, D_{6} = 49.
Since the sequence ends with 0, we only need to sum A and C, which yields
.
Solution by ~Cc2010cc2015
Video Solution by OmegaLearn
https://youtu.be/WpSpnx8PPnc?t=94
~pi_is_3.14
Video Solution
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.