3
$\begingroup$

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$?

  • 0
    I recently found a nice proof for the same. :-)2010-12-23

2 Answers 2

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