UGC NET CSE | June 2019 | Part 2 | Question: 3

Question

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

• A. $320$
• B. $480$
• C. $640$
• D. $768$

Comments

Ans $3)$

using inclusion-exclusion

Answer 1

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

Answer 2

According to the principle  of mutual inclusion-exclusion:

The number of strings either start with a $1$ bit or end with two bits $00 = 2^{9}+2^{8}-2^{7} = 640$