How many bit strings containing exactly eight $0$s and twelve $1$s have either all the $0$s consecutive, or all the $1$s consecutive?
My working :
There are $20$ positions $(8 + 12)$
Since there are $2$ possibilities for each position
Thus $2^{20}$
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Not following...say all the $1's$ are consecutive. Then the only pattern is $0^a1^{12}0^b$ where $a,b$ are non-negative integers that add to $8$. That's not very many cases! $\endgroup$– luluOct 9, 2016 at 13:04
-
$\begingroup$ Someone said this:First, lets count the number of bit strings that have all the 0s consecutive. In this case, there are 13 different ways of placing the 0s relative to the 1s (you can have between 0 and 12 ones first, then all the 0s, and then the remaining 1s) Next, the number of bit strings with all the 1s consecutive is 9, by the same logic as above.Finally, we have counted the strings where all the 0s and all the 1s are consecutive twice, which can happen in 2 ways (either the 0s first and then the 1s or the 1s first and then the 0s). All in all this gives 13+9−2=2013+9−2=20 bit strings $\endgroup$– Math.10Oct 9, 2016 at 13:08
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
For the case with all $1$s consecutive, we have $9$ possibilities:
11111111111100000000
01111111111110000000
00111111111111000000
.
.
.
00000000111111111111
For the case with all $0$s consecutive, we have $13$ possibilities.
00000000111111111111
10000000011111111111
11000000001111111111
.
.
.
11111111111100000000
Notice that we have double counted the following bit-strings:
00000000111111111111
11111111111100000000
Thus the total is $9 + 13 - 2 = 20$
-
$\begingroup$ I see, that makes everything clearer. Thank you :) $\endgroup$– Math.10Oct 9, 2016 at 13:10
$\begingroup$
$\endgroup$
1
An alternative way of counting: Put 12 ones and 8 zeroes in a circle, with the ones together and the zeroes together. If you start anywhere on the circle and read off the 20 bits in clockwise order from that position, then you get one of the strings you want to count. And every string that you want to count arises in this way exactly once.
Therefore the total number of strings is exactly the number of places you can start on the circle, that is, $20$.
answered Oct 9, 2016 at 13:51
hmakholm left over Monicahmakholm left over Monica
283k23 gold badges422 silver badges684 bronze badges