How many bit strings of length ten either start with a 1 bit or end with two…

Solution:

Use inclusion–exclusion to count bit strings of length ten that start with a 1 or end with 00.

• Count that start with a 1: fix the first bit as 1, the remaining 9 bits are free → 2^9 = 512.

• Count that end with 00: fix the last two bits as 00, the remaining 8 bits are free → 2^8 = 256.

• Count that both start with 1 and end with 00: fix first bit and last two bits, the remaining 7 bits are free → 2^7 = 128.

Apply inclusion–exclusion: 512 + 256 - 128 = 640. Therefore, there are 640 such bit strings.