1. ## Multiplication Principle

Use the generalized multiplication principle to show that the set {1,2,...,n} has exactly 2^n subsets.

Show that if you have a collection of 2^(n-1) + 1 subsets of {1,2,...,n}, then at least two of them are disjoint.

Can someone show this please? Thanks. I don't have a clue...

2. Hint :

Consider for example $\displaystyle A=\{1,2,3,4,5\}$ and the subsets $\displaystyle B=\{2,5\}=\emptyset,A$ . Denote:

$\displaystyle B:\quad 01001$

$\displaystyle \emptyset\;:\quad 00000$

$\displaystyle A:\quad 11111$

...

Fernando Revilla