Thread: 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...

Hint :

Consider for example and the subsets . Denote:







...


Fernando Revilla