How many subsets of $\{1, 2, …, n\}$ contain $1$ and how many don't?

Question

Consider the set $A = \{1, 2, …, n\}$

(a) How many subsets of A contain $1$?

I got $ 2^n - 2^{n-1}$

(b) How many subsets of A do not contain $1$?

I got $2^{n-1}$

(c) Use the pigeonhole principle and parts (a) and (b) to show that if we select more than half of the total subsets of A, then two of the sets selected will have the property that one is a subset of the other.

Answer 1

there are $n$ numbers out of which 1 is already selected. So we are left with $n-1$ numbers. If $B\subset A$ where $B=\{1, x: x\in A\}$ then noting that the number of such $B$ is same as number of subsets of a set of $n-1$ elements, we get $2^{n-1}$ as answer for (a).

For (b), the answer is total number of subsets of $A$ - total number of subsets that contains 1 = $2^n - 2^{n-1}=2^{n-1}$.

Answer 2

For every subset $A$ which contains $1$, there is a subset , namely $ A \setminus \lbrace 1 \rbrace $ which doesn't contain $1$ . This is a bijection. The subsets of $ \lbrace 1, \ldots , n \rbrace $ are $2^n$ and thus the answer to both $a)$ and $b)$ is $$ \frac{2^n}{2} = 2^{n-1} $$

Answer 3

Like WLOG said, consider the set A, and exclude element 1 so you have B={2,3,...,n}. Now, the cardinality of set A is n. And it follows that the cardinality of B is n-1. Then, if we make all of the possible subsets of B, there are 2^(n-1) of these. Which, does count both the number of subsets which contain 1, and the number of subsets which do not contain 1. This is because, in the former case, consider having all of the subsets of B, the power set before you. You decide to throw an identical object, call it 1, into all of the sets. Now, the cardinality of the individual subsets has changed, but that does not matter; what does matter is the cardinality of the power set, which has not change.

For the later case, it should be obvious why 2^(n-1) would count the number of subsets which do not contain 1.

The answer for part c is a little long, but it should help you get started if you consider n=2*q for some integer q>0. Then, consider the later half of the subsets being selected, that is the cardinality of subsets greater than or equal to q. Then, that's half of them selected, but the extra set you must pick should be from a subset of cardinality less than q... This should help you get started.

Answer 4

For part (c), suppose that we have $m$ different subsets of $A$, where $m > \frac{2^n}{2} = 2^{n-1}$. Now by part (b), we know that there are $2^{n-1}$ subsets of $A$ that don't contain a $1$; let's name them as: $$ S_1, S_2, \ldots, S_{2^{n-1}} $$ Using these $2^{n-1}$ subsets, notice that we can obtain the other $2^{n-1}$ subsets from part (a) by unioning each set with $\{1\}$. In other words, we can partition the set of all subsets of $A$ into $2^{n-1}$ pairs as follows: \begin{Bmatrix} \{S_1, S_1\cup \{1\}\}, \\ \{S_2, S_2 \cup \{1\}\}, \\ \vdots \\ \{S_{2^{n-1}}, S_{2^{n-1}} \cup \{1\}\} \end{Bmatrix} Now let the $m$ different subsets of $A$ be the pigeons and let the $2^{n-1}$ pairs be the holes. Then since $m > 2^{n-1}$, it follows by the Pigeonhole Principle that two of the pigeons will end up in the same hole so that for some $k \in \{1, \ldots, 2^{n-1}\}$, we have that $S_k$ and $S_k \cup \{1\}$ must be $2$ of the $m$ chosen subsets of $A$. Conveniently, these two subsets also happen to satisfy the desired property that $S_k \subset S_k \cup \{1\}$, as required. $~~\blacksquare$