GATE Overflow Test Series | Discrete Mathematics | Test 2 | Question: 5

Question

The number of bit strings of length $6$ that do not contain “$1111$” as a substring is $\_\_\_\_$

Answer 1

Total number of bit strings of length $6 = 2^6$ as each of the $6$ positions has $2$ options - $0$ or $1.$

Number of bit strings of length $6$ containing $1111$ as a substring = $8$

(001111, 011111, 101111, 111111, 111100, 111101, 111110, 011110)

$\therefore$ Total number of strings of length $6$ which does not contain $1111$ as a substring $= 64-8 =56$.

Comments

Number of bit strings of length $6$ containing $1111$ as a substring = $2^2$ $* 2!$ $= 8$, right?

---

For people who are wondering how to count number of bit strings of length 6 containing 1111 as a substring , following is one approach. Hope it is helpful for other aspirants too.

there are 4 mutually exclusive cases here

1. no. of bit strings of length 6 having substring of 4 ones – (6-4+1) = 3 strings

We should also consider cases of 5 ones and 6 ones as well as both contain substring 1111 

2. no. of bit strings having substring of 5 ones – ( 6-5+1 ) = 2 strings

3. no. of bit strings having 5 ones but not together – (101111, 111101 ) = 2 strings

4. no. of bit strings containing all 1’s = 1 string

Since all 4 cases are mutually exclusive we can add them and we get a total of 8 bit strings having substring 1111

---

2^2 for last 4 bit =”1”

and

2^2 for first 4 bit=”1”

 

total= 4+4=8