Difference between revisions of "2012 AMC 12B Problems/Problem 12"

Revision as of 07:46, 29 June 2023

Problem

How many sequences of zeros and ones of length 20 have all the zeros consecutive, or all the ones consecutive, or both?

$\textbf{(A)}\ 190\qquad\textbf{(B)}\ 192\qquad\textbf{(C)}\ 211\qquad\textbf{(D)}\ 380\qquad\textbf{(E)}\ 382$

Solutions

Solution 1

There are $\binom{20}{2}$ selections; however, we count these twice, therefore

$2\cdot\binom{20}{2} = \boxed{\textbf{(D)}\ 380}$ . The wording of the question implies D, not E.

However, MAA decided to accept both D and E.

Solution 2

Consider the 20 term sequence of $0$ 's and $1$ 's. Keeping all other terms 1, a sequence of $k>0$ consecutive 0's can be placed in $21-k$ locations. That is, there are 20 strings with 1 zero, 19 strings with 2 consecutive zeros, 18 strings with 3 consecutive zeros, ..., 1 string with 20 consecutive zeros. Hence there are $20+19+\cdots+1=\binom{21}{2}$ strings with consecutive zeros. The same argument shows there are $\binom{21}{2}$ strings with consecutive 1's. This yields $2\binom{21}{2}$ strings in all. However, we have counted twice those strings in which all the 1's and all the 0's are consecutive. These are the cases $01111...$ , $00111...$ , $000111...$ , ..., $000...0001$ (of which there are 19) as well as the cases $10000...$ , $11000...$ , $111000...$ , ..., $111...110$ (of which there are 19 as well). This yields $2\binom{21}{2}-2\cdot19=\boxed{\textbf{(E)}\ 382}$

Solution 3

First, we think of ways to make all the $1$ 's consecutive. If there are no consecutive $1$ 's, there are $\binom{20}{0}$ ways to order them. If there is one consecutive $1$ , there are $\binom{20}{1}$ ways to order them. If there are two consecutive $1$ 's, then there are $\binom{19}{1}$ ways to order them (We treat the two $1$ 's like a block, and then order that block with 18 other $0$ 's). Continuing in this fashion, there are $\binom{20}{0} + \binom{20}{1} + \binom{19}{1} + \cdots + \binom{1}{1} = 1 + 20 + 19 + \cdots + 2 + 1 = 210 + 1 = 211$ ways to order consecutive $1$ 's. From symmetry, there are also $211$ ways to order the $0$ 's. Now, from PIE, we subtract out the cases where both the $1$ 's and the $0$ 's are consecutive. We do this because when counting the ways to order the $1$ 's, we counted all of these cases once. Then, we did so again when ordering the $0$ 's. So, to only have all of these cases once, we must subtract them. If $1$ is the leftmost digit, then there are $20$ cases where all the $1$ 's and $0$ 's are consecutive (we basically are choosing how many $1$ 's are consecutive, and there are $20$ possibilities. All other digits become $0$ , which are automatically consecutive since the $1$ 's are consecutive. There are also $20$ cases when $0$ is the left-most digit. Thus, there are a total of $211 + 211 - 20 - 20 = \boxed{\textbf{(E)}\ 382}$ . But, from the way the problem is worded, it somewhat implies that the orderings must include both $1$ 's and $0$ 's, so the answer would then be $\boxed{\textbf{(D)}\ 380$ (Error compiling LaTeX. Unknown error_msg) after we subtract out the cases where the orderings are either all $1$ 's or all $0$ 's. But, since this is unclear, MAA accepted both $\boxed{\textbf{(D}\ 380}$ and $\boxed{\textbf{(E)}\ 382}$ as acceptable answers.

@@ Line 18: / Line 18: @@
 Consider the 20 term sequence of <math>0</math>'s and <math>1</math>'s.  Keeping all other terms 1, a sequence of <math>k>0</math> consecutive 0's can be placed in <math>21-k</math> locations. That is, there are 20 strings with 1 zero, 19 strings with 2 consecutive zeros, 18 strings with 3 consecutive zeros, ..., 1 string with 20 consecutive zeros. Hence there are <math>20+19+\cdots+1=\binom{21}{2}</math> strings with consecutive zeros. The same argument shows there are <math>\binom{21}{2}</math> strings with consecutive 1's. This yields <math>2\binom{21}{2}</math> strings in all. However, we have counted twice those strings in which all the 1's and all the 0's are consecutive. These are the cases <math>01111...</math>, <math>00111...</math>, <math>000111...</math>, ..., <math>000...0001</math> (of which there are 19) as well as the cases <math>10000...</math>, <math>11000...</math>, <math>111000...</math>, ..., <math>111...110</math> (of which there are 19 as well). This yields <math>2\binom{21}{2}-2\cdot19=\boxed{\textbf{(E)}\ 382}</math>
+==Solution 3==
+First, we think of ways to make all the <math>1</math>'s consecutive. If there are no consecutive <math>1</math>'s, there are <math>\binom{20}{0}</math> ways to order them. If there is one consecutive <math>1</math>, there are <math>\binom{20}{1}</math> ways to order them. If there are two consecutive <math>1</math>'s, then there are <math>\binom{19}{1}</math> ways to order them (We treat the two <math>1</math>'s like a block, and then order that block with 18 other <math>0</math>'s). Continuing in this fashion, there are <math>\binom{20}{0} + \binom{20}{1} + \binom{19}{1} + \cdots + \binom{1}{1} = 1 + 20 + 19 + \cdots + 2 + 1 = 210 + 1 = 211</math> ways to order consecutive <math>1</math>'s. From symmetry, there are also <math>211</math> ways to order the <math>0</math>'s. Now, from PIE, we subtract out the cases where both the <math>1</math>'s and the <math>0</math>'s are consecutive. We do this because when counting the ways to order the <math>1</math>'s, we counted all of these cases once. Then, we did so again when ordering the <math>0</math>'s. So, to only have all of these cases once, we must subtract them. If <math>1</math> is the leftmost digit, then there are <math>20</math> cases where all the <math>1</math>'s and <math>0</math>'s are consecutive (we basically are choosing how many <math>1</math>'s are consecutive, and there are <math>20</math> possibilities. All other digits become <math>0</math>, which are automatically consecutive since the <math>1</math>'s are consecutive. There are also <math>20</math> cases when <math>0</math> is the left-most digit. Thus, there are a total of <math>211 + 211 - 20 - 20 = \boxed{\textbf{(E)}\ 382}</math>. But, from the way the problem is worded, it somewhat implies that the orderings must include both <math>1</math>'s and <math>0</math>'s, so the answer would then be <math>\boxed{\textbf{(D)}\ 380</math> after we subtract out the cases where the orderings are either all <math>1</math>'s or all <math>0</math>'s. But, since this is unclear, MAA accepted both <math>\boxed{\textbf{(D}\ 380}</math> and <math>\boxed{\textbf{(E)}\ 382}</math> as acceptable answers.
 == See Also ==

2012 AMC 12B (Problems • Answer Key • Resources)
Preceded by Problem 11	Followed by Problem 13
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

Page

Toolbox

Search