TIFR CSE 2019 | Part A | Question: 1

Question

Let $X$ be a set with $n$ elements. How many subsets of $X$ have odd cardinality?

• A. $n$                                        
• B. $2^n$
• C. $2^{n/2}$
• D. $2^{n-1}$
• E. Can not be determined without knowing whether $n$ is odd or even

Answer 1

$X$ is a set of n elements then there are total $2^n$ subsets out of which $2^{n-1}$ have odd cardinality and $2^{n-1}$ have even cardinality.

$\text{D}$ is correct option.

Answer 2

Quick Proof

Consider the binomial expansion of (1-x)^n and put x=0

Answer 3

Following cases must be included

if n=0 ans is 0 since cardinality of empty set is zero thus no odd subset

if n>0 ans is $2^{n-1}$ number of odd cardinality set

Final answer E

Answer 4

Exactly half of the elements of $\mathcal{P}(A)$ are odd-sized.

 

Fix an element $a\in A$ (this is the point where $A\ne\emptyset$ is needed).
Then $$S\mapsto S\operatorname{\Delta}\{a\}$$ symmetric difference is a bijection from the set of odd subsets to the set of even subsets.

For more on this visit here and here