0
$\begingroup$

How many bit strings (Consists of only 0 or 1) of length 8 contain either three consecutive 0s or four consecutive 1s?

I am getting answer 256 but the provided answer is 147 . Can anyone explain why it is 147?

Attempt

Case 1. Let's take 3 zeros as a single unit. They can be placed in 6 positions (2 sides positions and 4 positions in between 5 elements) rest of the five elements can be selected in $2^5$ ways (they can either be 0 or 1). So total $n_1=6\cdot 2^5$ but here you can have 8 ways to get 4 consecutive 1s..

In same way for Case 2. $n_2$ will be $5\cdot 2^4$ and here also we can find 8 ways to get 3 consecutive 0s. Thus total $= n_1+n_2-(8+8)=272-16=256$.

$\endgroup$
  • 3
    $\begingroup$ Can you show your work? It would be more instructive to see where you went wrong in your calculation than to just give you the proper answer. $\endgroup$ – A.E Sep 7 '14 at 16:42
  • 1
    $\begingroup$ Inclusion-Exclusion, I guess you counting twice some cases, like the string '00001111' $\endgroup$ – Snufsan Sep 7 '14 at 16:42
  • $\begingroup$ @A.E case-1-->lets take 3 0s as a single unit they can be placed in 6 positions (2 sides positions and 4 positions in between 5 elements) rest of the five elements can be selected in 2^5 ways(they can either be 0 or 1). so total n1=6x2^5 but here you can have 8 ways to get 4 consecutive 1s..in same way for case 2 --> n2 will be 5x2^4and here also we can find 8 way to get 3 consecutive 0s. thus total= n1+n2-(8+8)=272 $\endgroup$ – user131459 Sep 7 '14 at 17:07
2
$\begingroup$

Lets use inclusion-exclusion method.

First we find the number of bit-strings from size of $n$ that doesn't contain the sequence '000'. We will construct recursion formula, let $F(n)$ be that number.

  • If the first bit is '1' then the rest is just a string that doesnt contain '000' from size $n-1$
  • If the first bits is '01' then the rest is just a string that doesnt contain '000' from size $n-2$
  • If the first bit is '001' then the rest is just a string that doesnt contain '000' from size $n-2$

Therfore we get: $F(n) = F(n-1)+F(n-2)+F(n-3)$

With the initial conditions $F(0) =1, F(1) =2, F(2) =2^2$

With te same method we get: $G(n) = G(n-1)+G(n-2)+G(n-3)+G(n-4)$

With the initial conditions $G(0) =1, G(1) =2, G(2) =2^2, G(3)=2^3$

Where $G(n)$ is the number of bit-strings from size of $n$ that doesn't contain the sequence '1111'.

Now, by opening the recursion up we get $F(8)= 149$ and $G(8)=208$

So if we define:

  • A = bit-string of size 8 that contain '000'
  • B = bit-string of size 8 that contain '1111'

and by what we calculated we have $|A| = 2^8-F(8)$ and $|B| = 2^8-G(8)$

What left to complete inclusion exclusion is to find the size of $|A\cap B|$, which is easy since the only strings that satisfy both are: '00001111' , '11110000', '11111000', '00011111', '00011110', '10001111', '01111000', '11110001'

Now the desiered number is $|A|+|B|-|A \cap B|$

$\endgroup$
  • $\begingroup$ According to this solution answer is 211...but provided answer is 147 $\endgroup$ – user131459 Sep 7 '14 at 17:21
  • $\begingroup$ I had calculation error, it's indeed 147: $|A|=256-149=107$ , $|B|=256-208=48$ and finally we have: $107+48-8=147$ $\endgroup$ – Snufsan Sep 7 '14 at 17:32
  • 1
    $\begingroup$ great explanation, thanks $\endgroup$ – Inoryy Dec 27 '14 at 14:07

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.