How many bit strings of length 10 contain either five con- secutive 0s or five consecutive 1s?
Answers
Observe first 5 consecutive 0s
Summation rule: the first 5 consecutive 0’s could start at position 1, 2, 3, 4, 5, or 6
Start at first position
Other 5 bits can be anything: 2^5 = 32
Start at second position
First bit must be a 1
There are various possibilities that can be included in it.
Remaining bits can be anything: 2^4 = 16
Start at third position
Second bit must be a 1 due to above mentioned reason.
First bit and last 3 bits can be anything: 2^4 = 16
Starting at 4,5 and 6 positions
Same as starting at positions 2 or 3: 16 each
Total = 32 + 16 + 16 + 16 + 16 + 16 = 112
The five consecutive 1’s ensue the same pattern, and have different like 112 possibilities
There would be two cases counted twice (that we thus need to exclude): 0000011111 and 1111100000
Total = 112 + 112 – 2 = 222