using inclusion-exclusion

Dark Mode

4,335 views

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.$