Question

How many bitstrings of length 10 contain three consecutive 0’s or 4 consecutive 1’s? How many bitstrings of length 10 contain two sets of 3 consecutive 0’s or two sets of 3 consecutive 1’s?

Answer 1

Answer:

147 bitstrings.

Step-by-step explanation:

To start with, we will compute the number of bit strings that has 3 consecutive 0's.

For each of the consecutive 0's, they can start at either 1st, 2nd, 3rd or 4th positions (because there are eight positions)

If we begin from the 1st position, there will be strings in the form of 000xxxxx

The other positions can be anything, count= 25 =32.

If we begin from the 2nd position, there will be strings in the form of 1000xxxx.

Note that the 1st position must contain 1, otherwise there will be more than one count strings.

The remaining 4 positions can be anything, count= 24 = 16.

If we begin from the 3rd position, there will be strings in the form of x1000xxx.

Note that the 2nd position must contain 1, or there will be more than one count strings as in the first scenario.

The remaining 4 positions can be anything, count= 24=16.

If we begin from the 4th, 5th, or 6th position, it would be the same analysis.

Therefore,

total count= 32 + 16 + 16 + 16 + 16 +16 = 112.

From the analysis done so far, we have double counted these 5 strings: 00010000, 00010001, 00001000, 00011000, 10001000

So, the actual strings that contain 3 consecutive 0's is 112-5 = 107.

If we also calculate the number of strings with 4 consecutive 1's, we will have: 16 + 8 + 8 + 8 + 8 = 48.

Therefore, there are 8 strings that we have double counted and they are: 11110000, 11110001, 11111000, 01111000, 00011110, 00011111, 00001111, 10001111.

So, for our final answer, the total number of bit strings of length 8 that contain either three consecutive 0's or four consecutive 1's is 107 + 48 - 8= 147.