Question 21

Mathematics Boolean algebra Hard

The number of bit strings of length 10 that contain either five consecutive 0 or five consecutive 1

(A) 64
(B) 112
(C) 220
(D) 222
View Dynamic Solution & Explanation
Correct Solution: Option D

Step-by-step Solution:

The correct calculation process leads to the final answer 222.

Explanation:

1. Bit Strings with Five Consecutive 0's:
The 5 consecutive 0's can start at any of the positions 1 through 6, giving 6 possibilities for the starting position.
For each of these 6 starting positions:
For positions 1, 2, 3, 4, 5, and 6, the remaining bits can be any combination of 0's and 1's.
The calculations are as follows:
Starting at position 1: The remaining 5 bits can be anything, so there are \( 2^5 = 32 \) possibilities.
Starting at position 2: The first bit must be 1 (to avoid overlap), leaving \( 2^4 = 16 \) possibilities.
Starting at positions 3, 4, 5, and 6: Same logic as position 2, leaving 16 possibilities for each.
Total possibilities for 5 consecutive 0's: \( 32 + 16 + 16 + 16 + 16 + 16 = 112 \).

2. Bit Strings with Five Consecutive 1's:
The process is identical to that of consecutive 0's, so the number of bit strings containing five consecutive 1's is also \( 112 \).

3. Exclusion of Double-counted Cases:
There are two cases where both five consecutive 0's and five consecutive 1's overlap:
\( 0000011111 \) and \( 1111100000 \).
We subtract these 2 double-counted cases.

4. Final Total:

The total number of valid bit strings is: \[ 112 + 112 - 2 = 222 \]
Thus, the correct final answer is: \[ \boxed{222} \]