The Gateway to Computer Science Excellence
+1 vote
315 views

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

  1. $320$
  2. $480$
  3. $640$
  4. $768$
in Combinatory by Veteran (424k points)
edited by | 315 views
0
Ans $3)$

using inclusion-exclusion

2 Answers

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

by Active (1.6k points)
+1 vote

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$

by Veteran (54.7k points)
edited by
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,648 questions
56,430 answers
195,209 comments
99,924 users