0
$\begingroup$

So I'm a little bit stuck on how to continue about this problem. "How many bit strings of length eight do not contain six consecutive 0s?"

So what I did first is I found the total amount of bit strings 2^8 = 256.

I know that there must be at least one string with 8 consecutive 0's, at least one with 7 consecutive 0's, and one with at least 6 consecutive 0's. But how do I find how many of each is contained without listing out all the 8 bit strings?

Thanks.

$\endgroup$
  • $\begingroup$ Hint: your problem is equivalent to counting how many ways there are to fit $0, 1,$ or $2$ pins in $8$ holes... $\endgroup$ – A.P. Mar 26 '15 at 23:04
  • $\begingroup$ Count the strings with at least $6$ consecutive $0$ (bad strings), and subtract from $2^8$. For bigger numbers we might have to get fancier, but your cases approach works fine here. There is $1$ string with $8$ consecutive $0$'s. There are $2$ with $7$ consecutive but not $8$, namely $10000000$ and the reversal of this. For $6$ consecutive but not $7$, the $0$'s could start at the beginning. So we get $0000001x$, where $x$ is anything, so $2$. Then there is $10000001$. Finally, there is $x1000000$ so $2$ more. Add up. $\endgroup$ – André Nicolas Mar 26 '15 at 23:05
1
$\begingroup$

You are saying (correctly) that the number you are looking for is $2^8-B$ where $B$ is the number of bad strings, i.e., those containing six consecutive zeros. And to know what $B$ is you say correctly that it is the sum $B_6+B_7+B_8$, where $B_k$ is the number of $8$-bit strings containing $k$ consecutive zeros. Now, what is $B_8$ (hint: that is very easy to answer). What is $B_7$ (hint: not a large number at all, you can list all such strings). What is $B_6$ (hint: a slightly bigger number, but do you notice some symmetry?)

$\endgroup$
0
$\begingroup$

Well B8 is obviously 1. B7 is 2, since I know theres 00000001 and 10000000, but I seem to be stuck on 6. Theres 100000011, 000000111, 110000001,and 111000000. so would I minus them all? There needs to be a more mathematical approach to this, other than me thinking of all the scenarios in which I could get a row of 6 consecutive 0's. Is there one?

$\endgroup$
  • $\begingroup$ there aren't too many scenarios to get six zeros. If you list them all, you may notice a pattern for a more elegant solution. $\endgroup$ – Ittay Weiss Mar 27 '15 at 0:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.