edited by
1,555 views

2 Answers

Best answer
4 votes
4 votes

First calculated How many bit strings of length eight contain six consecutive 0's ?

A) 0 0 0 0 0 0  __ __               -----> 4

B)  __ 0 0 0 0 0 0 __               -----> 4

C) __ __ 0 0 0 0 0 0                -----> 4

 

| A ∩ B | = 0 0 0 0 0 0 __ __  ∩  __ 0 0 0 0 0 0 __  = 0 0 0 0 0 0 0 __         -----> 2

| A ∩ C | = 0 0 0 0 0 0 __ __  ∩  __ __ 0 0 0 0 0 0  = 0 0 0 0 0 0 0 0           -----> 1

| B ∩ C | = __ 0 0 0 0 0 0 __  ∩  __ __ 0 0 0 0 0 0  = __ 0 0 0 0 0 0 0          -----> 2

| A ∩ B ∩ C | = 0 0 0 0 0 0 __ __  ∩  __ 0 0 0 0 0 0 __  ∩  __ __ 0 0 0 0 0 0  = 0 0 0 0 0 0 0 0  -----> 1

 

 

| A U B U C | = | A | + | B | + | C | - | A ∩ B | - | A ∩ C | - | B ∩ C | + | A ∩ B ∩ C|

                   =       4   +    4   +   4  -  2       -    1  -  2  +  1  = 12 - 5 + 1 = 8

 

total bit strings possible with length 8 = 28 = 256      

bit strings of length eight do not contain six consecutive 0's = 256-8 = 248

selected by
1 votes
1 votes

Trick is first of all we will find all 6 consecutive 0's then we will subtract that from total 8 bit string.

total 8 bit string = (6 consecutive 0's) + (not 6 consecutive 0's).

Consider the following:

[0 0 0 0 0 0] * *
* [0 0 0 0 0 0] *
* * [0 0 0 0 0 0]

Each of the stars can be a zero or one.

  • The first case, we have 4 combinations (where each star is either 00 or 11).

           ex: [0 0 0 0 0 0] 0 0

         [0 0 0 0 0 0] 0 1

         [0 0 0 0 0 0] 1 0

                  [0 0 0 0 0 0] 1 1

  • The second case, again can have four possibilities. However, you should exclude those we counted in the first case. They are 0 0 0 0 0 0 0 0 and 0 0 0 0 0 0 0 1. So only 2 distinct possibilities.

           i.e. 1 0 0 0 0 0 0 1 and 1 0 0 0 0 0 0 0

  • The third case has only 2 new possibilities, which are 0 1 0 0 0 0 0 0 and 1 1 0 0 0 0 0 0.

So the answer to your question is 28−(4+2+2)=248

 I hope you got your answer.

Related questions

0 votes
0 votes
0 answers
1