If a set contain $(2n+1)$ elements and if the number of subsets which contain at most n elements is 4096, then what is the value of $n$?
If a set contain $(2n+1)$ elements and if the number of subsets which contain at most n elements is 4096, then what is the value of $n$?
3
$\begingroup$
elementary-set-theory
-
0I recently found a nice proof for the same. :-) – 2010-12-23
2 Answers
7
There are $2^{2n + 1}$ subsets in total. Now note that the function which takes a subset to its complement is a bijection, and that a subset has $n$ or fewer elements if, and only if, its complement has more than $n$ elements. Thus the number of subsets with $n$ or fewer elements is equal to the number with more than $n$; thus the number of each is $2^{2n + 1}/2 = 2^{2n}$. Now solve for $n$.
1
Use the identity $(1+1)^n= n_{C_0}+n_{C_1}+\dots+n_{C_n}$ and the fact that $n_{C_r}=n_{C_{n-r}}$.