ISRO CSE 2014 | Question: 19

Question

The number of bit strings of length $8$ that will either start with $1$ or end with $00$ is?

• A. $32$              
• B. $128$             
• C. $160$          
• D. $192$

Comments

You can apply Mutual Exclusion -Inclusion principle

and easily find the right answer

---

Detailed Video Solution: https://www.youtube.com/watch?v=PL0tnU76TLM&t=477s

---

Another Video Solution: https://www.youtube.com/watch?v=ylClXdsxSCA&t=336s

Answer 1

string starting with 1 - 8 places 1 place fixed .7 places have 2 choices . 2^7=128

ending with 00- 8 places 2 fixed. =2^6=64

common strings will be there that have been counted twice are . starting with 1 and ending with 00. such number of string will be .

fix 3 position rest have 2 choices=32

total = 128+64-32=160

Comments

i did not get it .. plz can u elaborate?

---

Good explanation

---

This comes under Discrete Mathematics

We need to follow the subtraction rule |AUB| = |A| + |B| - |A intersect B|

A => Start with 1; 1 place is fixed, therefore (8-1) = 7; 7 places can take two choices 0 and 1, so 2^7 = 128

B => Ends with 00; 2 places is fixed, therefore (8-2) = 6; 6 places can take two choices 0 and 1, so 2^6 = 64

|A intersect B| => Start with 1; and end with 00; 3 places is fixed, therefore (8-3) = 6; 5 places can take two choices 0 and 1, so 2^5 = 32

As per subtraction rule A and B are not disjoint sets so the intersection part needs to be subtracted.

which is 128+64-32 = 160, the answer.

For more clarification, visit https://www.inf.ed.ac.uk/teaching/courses/dmmr/slides/14-15/Ch6.pdf

---

Gud

Answer 2

Here we can apply Mutual Inclusion-Exclusion, (no need to worry if u don't know)

For sets we know n(a U b)= n(a) + n(b) - n(a ∩ b)

in this answer    # = Total number of .

 

# bit strings of length 8 that will start with  1 (let it be n(a)) = 2^7 = 128 (because we have 1 choice for 1st position and we have 2 choices each for other 7 position).

# bit strings of length 8 that will end with  00 ( let it be n(b))= 2^6 = 64 (similar reason as above)

Now in both the above bit strings we have common bit strings when string start with 1 and end with 00, and we have to count this only once to cover all cases, so

# bit strings of length 8 that will start and end with  00 (  n(a ∩ b)) = 2^5 = 32 .

#bit strings of length 8 that will start  with 1 or end with 00= n(a U b)= n(a) + n(b) - n(a ∩ b) = 128+ 64 - 32 = 160

so, 160 is the answer