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"

(→‎Solution 2)
 
(7 intermediate revisions by 4 users not shown)
Line 5: Line 5:
 
<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 11: 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\cdot\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 <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=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 19: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"