$|X| = n \geq 2$. Show that among any $n+2$ subsets of the set $X$, there exist two subsets that have the same number of elements.

Question

Can someone help me with this question? I'm having trouble solving this problem. I don't know where start.

Let $X$ be a set containing $n \geq 2$ different integers. Show that among any $n+2$ subsets of the set $X$, there exist two subsets that have the same number of elements.

I know that the pigeonhole principle states that if you have $x$ items to put into $y$ boxes, and $x>y$, at least one box is going to have more than one item. My idea for this problem is that the possible sizes of subsets of $X$ are my "boxes" and the $n+2$ subsets are my "items". But I don't really know how to apply this rule. :|

Answer 1

First, you must know how many possible sizes of subsets are there. There are subsets that have sizes $0$, $1$, $2$, $3$, $\dots$, $n$, so there are $n+1$ sizes possible. We have $n+2$ subsets. By applying the pigeon-hole principle, there must be at least two subsets that have the same size.

Just look at the subsets' sizes as the "boxes", and the subsets as the "items".