using inclusion-exclusion

The Gateway to Computer Science Excellence

+2 votes

How many bit strings of length ten either start with a $1$ bit or end with two bits $00$ ?

- $320$
- $480$
- $640$
- $768$

+3 votes

Answer - **(3) 640**

The problem can be divided into two parts,

**Part 1** - No. of bit strings of length 10 that start with bit 1.

So, the strings will be of the form

**1 _ _ _ _ _ _ _ _ _**

which means $9$ empty places to fill with either $0$ or $1$, hence $2^9$ ways.

**Part 2** - No. of bit strings of length 10 that end with two bit zeros.

Now, we have already counted the strings that end with two bit zeros in the part 1, but all those strings were starting with a bit 1. So, we still haven't counted the bit strings that start with a zero, and end with two zeroes. So, such strings will be of the form

**0 _ _ _ _ _ _ _ 0 0**

which means 7 empty places to fill with either 0 or 1, hence $2^7$ ways.

Hence, total no. of ways = Part 1 + Part 2 (because OR)

$ = 2^9 + 2^7$

$ = 2^7 (2^2 + 1)$

$ = 2^7 (5) = 640$

One more way to solve this would be,

Let, $N_A$ = No. of bit strings of length 10 that start with 1 = $2^9$

$N_B$ = No. of bit strings of length 10 that end with two zeros = $2^8$

So, $N_{A \cap B}$ = No. of bit strings of length 10 that start with 1 **and **end with two zeros = $2^7$

Now, by inclusion-exclusion principle,

No. of bit strings of length 10 that start with 1 **OR **end with two zeros,

$N_{A \cup B} = N_A + N_B - N_{A \cap B} = 2^9 + 2^8 - 2^7 = 2^7 (4 + 2 - 1) = 2^7 \cdot 5 = 640.$

52,345 questions

60,517 answers

201,937 comments

95,368 users