Kenneth Rosen Edition 6th Exercise 6.6 Question 13 (Page No. 449)

Question

How many bit strings of length eight do not contain six consecutive 0's?

Comments

248  ??

Answer 1

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 = 2⁸ = 256      

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

Comments

I didn't get how you calculated the intersection of two strings part. Please elaborate more

---

$A_1∩A_2$ consists of those bit strings in which the last six and middle six digits of the bit string are zeros, so the last seven digits of the bit string are zeros.

 $A_2∩A_3$ consists of those bit strings in which the first six and middle six digits of the bit string are zeros, so the first seven digits of the bit string are zeros.

The set $A_1∩A_3$ consists of those bit strings in which the first six and last six digits of the bit string are zeros, so each of the eight digits of the bit string is a zero.

The set $A_1∩A_2∩A_3$ consists of those bit strings in which the first six, middle six, and last six digits of the bit string are zeros, so each of the eight digits of the bit string is a zero.

---

@ Ayush Upadhyaya , updated in my answer

Answer 2

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 2⁸−(4+2+2)=248

 I hope you got your answer.

Comments

@ Rishav, yes your answer and approach is right... But it's good that calculate via formula why because if A intersection B ( or some other ) have more no of combination ( let say grater than 10 ) , then you can't directly calculate, Distinct possibilities' of B.

---

@Shaik I am not against formulas. Many people do it with formulas and some do it with their intuitions. It depends what suits. You are doing the same thing in your formula which I have done. I had to illustrate it better because @Ayush was not getting your solution.

---

Brother i personally against the formulas, but in this type of questions we can't do it always with our intuitions, if we do with our intuitions it takes more time. and i am not talking about this particular question in this type of questions, i am talking in general of this type of questions