Difference between revisions of "2019 AMC 10B Problems/Problem 25"
Shurong.ge (talk | contribs) (→Solution 1 (recursion)) |
(Added Solution 3) |
||
| Line 27: | Line 27: | ||
Summing the four cases gives <math>1+28+35+1=\boxed{\textbf{(C) }65}</math>. | Summing the four cases gives <math>1+28+35+1=\boxed{\textbf{(C) }65}</math>. | ||
| + | |||
| + | ==Solution 3 (casework and blocks)== | ||
| + | We can simplify the original problem into a problem where there are <math>2^{17}</math> 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 <math>0</math>s, <math>1</math>s, and <math>11</math>s. Now, we use casework: | ||
| + | '''Case 1''': Alternating 1s and 0s. There is simply 1 way to do this: <math>0101010101010101010</math>. | ||
| + | Now, we note that there cannot be only one block of <math>11</math> in the entire sequence, as there must be zeroes at both ends and if we only include 1 block, of <math>11</math>s this cannot be satisfied. This is true for all odd numbers of <math>11</math> blocks. | ||
| + | '''Case 2''': There are 2 <math>11</math> blocks. Using the zeroes in the sequence as dividers, we have a sample as <math>0110110101010101010</math>. We know there are 8 places for <math>11</math>s, which will be filled by <math>1</math>s if the <math>11</math>s don't fill them. This is <math>{8\choose2} = 28</math> ways. | ||
| + | '''Case 3''': Four <math>11</math> blocks arranged. Using the same logic as Case 2, we have <math>{7\choose4} = 35</math> ways to arrange four <math>11</math> blocks. | ||
| + | '''Case 4''': No single <math>1</math> blocks, only <math>11</math> blocks. There is simply one case for this, which is <math>0110110110110110110</math>. | ||
| + | |||
| + | Adding these four cases, we have <math>1+28+35+1=\boxed{\textbf{(C) }65}</math> as our final answer. | ||
| + | |||
| + | ~Equinox8 | ||
==Video Solution== | ==Video Solution== | ||
Revision as of 20:57, 7 May 2020
- 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 
with the only possible sequence being 
and 
with the only two possible sequences being 
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 (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
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. 
