Question

4. [6 marks] (Basic Counting) How many bit strings of length 10 contain either five consecutive 0s or five consecutive 1s?

Answer 1

•Consider 5 consecutive 0s first

•Sum rule: the 5 consecutive 0’s can start at position 1, 2, 3, 4, 5, or 6

–Starting at position 1

•Remaining 5 bits can be anything: 25 = 32

–Starting at position 2

•First bit must be a 1

–Otherwise, we are including possibilities from the previous case!

•Remaining bits can be anything: 24 = 16

–Starting at position 3

•Second bit must be a 1 (same reason as above)

•First bit and last 3 bits can be anything: 24 = 16

–Starting at positions 4 and 5 and 6

•Same as starting at positions 2 or 3: 16 each

–Total = 32 + 16 + 16 + 16 + 16 + 16 = 112

•The 5 consecutive 1’s follow the same pattern, and have 112 possibilities

•There are two cases counted twice (that we thus need to exclude): 0000011111 and 1111100000

•Total = 112 + 112 – 2 = 222