Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2012 AMC 12B Problems/Problem 12"
 
(10 intermediate revisions by 6 users not shown)
Line 1: Line 1:
 +
==Problem==
 +
 
How many sequences of zeros and ones of length 20 have all the zeros consecutive, or all the ones consecutive, or both?
 
How many sequences of zeros and ones of length 20 have all the zeros consecutive, or all the ones consecutive, or both?
  
 
<math>\textbf{(A)}\ 190\qquad\textbf{(B)}\ 192\qquad\textbf{(C)}\ 211\qquad\textbf{(D)}\ 380\qquad\textbf{(E)}\ 382</math>
 
<math>\textbf{(A)}\ 190\qquad\textbf{(B)}\ 192\qquad\textbf{(C)}\ 211\qquad\textbf{(D)}\ 380\qquad\textbf{(E)}\ 382</math>
  
−
==Solution==
+
==Solutions==
  
 
===Solution 1===
 
===Solution 1===
Line 9: Line 11:
 
There are <math>\binom{20}{2}</math> selections; however, we count these twice, therefore
 
There are <math>\binom{20}{2}</math> selections; however, we count these twice, therefore
  
−
<math>2*\binom{20}{2} = 380</math>. The wording of the question implies D not E.
+
<math>2\cdot\binom{20}{2} = \boxed{\textbf{(D)}\ 380}</math>. The wording of the question implies D, not E.
  
−
MAA decided to accept both D and E, however.
+
However, MAA decided to accept both D and E.
  
 
===Solution 2===
 
===Solution 2===
  
−
Consider the 20 term sequence of 0's and 1'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=382</math> so that the answer is <math>\framebox{E}</math>.
+
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.
 +
 
 +
 
 +
===Solution 4===
 +
 
 +
We consider two cases, and subtract their overcount.
 +
 
 +
 
 +
Case <math>1</math>: Consecutive <math>0</math>s
 +
 
 +
If we have one consecutive <math>0</math>, then we have <math>20</math> ways.
 +
If we have two consecutive <math>0</math>s, then we have <math>19</math> ways by thinking of the two consecutives as a block.
 +
Continuing this pattern, if we have twenty consecutive <math>0</math>s, then we have only <math>1</math> way.
 +
 
 +
Therefore, we have
 +
<math>20+19+\cdots+1=\binom{21}{2}</math> ways for this case.
 +
 
 +
 
 +
Case <math>2</math>: Consecutive <math>1</math>s
 +
 
 +
Notice that if we just swap every <math>0</math> to a <math>1</math> in the previous case, we also have a valid arrangement.
 +
Hence, we also have <math>20+19+\cdots+1=\binom{21}{2}</math> ways for this case.
 +
 
 +
 
 +
Overcount:
 +
Notice that we can have BOTH the <math>0</math>s and the <math>1</math>s be consecutive. These are the cases <math>01111...</math>, <math>00111...</math>, <math>000111...</math>, ..., <math>000...0000</math> which gives us <math>20</math> ways being overcounted. If we invert the <math>0</math>s to <math>1</math>s, we similarly have <math>20</math> more ways, hence we need to subtract <math>40</math> from our total count. (Note: this method of overcounting subtracts out the all <math>0</math>s and the all <math>1</math>s case since the problem implies that there needs to be at least one of each)
 +
 
 +
 
 +
So we have <math>210 + 210 - 40 = 380</math> ways which gives us <math>\boxed{\textbf{(D)}\ 380}</math>.  
 +
 
 +
~xHypotenuse
 +
 
  
 
== See Also ==
 
== See Also ==

Latest revision as of 20:15, 5 May 2024

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}$ 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.


Solution 4

We consider two cases, and subtract their overcount.


Case $1$: Consecutive $0$s

If we have one consecutive $0$, then we have $20$ ways. If we have two consecutive $0$s, then we have $19$ ways by thinking of the two consecutives as a block. Continuing this pattern, if we have twenty consecutive $0$s, then we have only $1$ way.

Therefore, we have $20+19+\cdots+1=\binom{21}{2}$ ways for this case.


Case $2$: Consecutive $1$s

Notice that if we just swap every $0$ to a $1$ in the previous case, we also have a valid arrangement. Hence, we also have $20+19+\cdots+1=\binom{21}{2}$ ways for this case.


Overcount: Notice that we can have BOTH the $0$s and the $1$s be consecutive. These are the cases $01111...$, $00111...$, $000111...$, ..., $000...0000$ which gives us $20$ ways being overcounted. If we invert the $0$s to $1$s, we similarly have $20$ more ways, hence we need to subtract $40$ from our total count. (Note: this method of overcounting subtracts out the all $0$s and the all $1$s case since the problem implies that there needs to be at least one of each)


So we have $210 + 210 - 40 = 380$ ways which gives us $\boxed{\textbf{(D)}\ 380}$.

~xHypotenuse


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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2012_AMC_12B_Problems/Problem_12&oldid=219042"