Determining the number of subsets of a set with a specific property

[jdinatale]

I found an example like the problem asks, but I'm still trying to show the first part. You want the maximum number of subsets such that you can guarantee none are pairwise disjoint.

I'm trying to apply my specific case to the whole problem. For a set with 3 elements, I chose all of the sets with 2 elements, \binom{3}{2} and all of the sets with 3 elements, \binom{3}{3}, which is 4 sets.

In general, for an set with n elements, would I want to choose all sets of with n - 1 elements, which would be \binom{n}{n - 1} = n of them and the set with n elements which there is \binom{3}{3} = 1 of them.

But that's only n + 1 sets, when I want 2^{n - 1} sets.

I know that \binom{n}{0} + \binom{n}{1} + \binom{n}{2} + ... + \binom{n}{n} = 2^n, which is really close to what I want to show.

http://i3.photobucket.com/albums/y89/jdinatale/Joseph-5.png

 

[jbunniii]

For an example where equality holds for general n, consider this: how many subsets of {1,2,...,n} contain 1?

To prove the inequality, consider this: if the collection contains a set A, can it also contain the complement of A?