Jest Exam sample question-3

Question

How many subsets of even cardinality does an n-element set have ? Justify answer.

Please give a proof if possible.This is part of subjective JEST paper.

Answer 1

Let the subset be denoted as a n-bit sequence of 0s and 1s

A 0 at the ith position indicates absence of the ith element

A 1 at the jth position indicates presence of the jth element

For example, let the set be {1,2,3}

Then {1,2} can be represented as 110

{1,2,3} can be represented as 111

and so on

 

Now the number of subsets of even cardinality in an n-element set  = number of n bit strings with an even number of ones

 number of n bit strings with an even number of ones = number of n bit strings with an odd number of ones

=>  number of n bit strings with an even number of ones = (number of different n bit strings)/2 = $2^{n-1}$