# The pigeonhole principle(?)

I have this question that seems to be an application of the Pigeonhole Principle, but I can't see how.

Let $n\geq3$. Consider the set $S=\{1,2,\ldots,n\}$ and $2n+1$ nonempty random subsets of $S$. Prove that there are at least three of those subsets $B_1,B_2,B_3$ such that $(\forall i\neq j)B_i\not\subset B_j$.

How can I apply the pigeonhole principle for this?Is the straightforward approach any good? I am asking because the way the statement is, a proof by contradiction seems more appropriate...

I tried constructing the three sets out of a given random choice of subsets: Say $A_1,A_2,...,A_{2n+1}$ are the 2n+1 subsets. Since the choice is random, we can consider that a subcollection exists, say A,B,...,C such that these sets have at least one element of S not in common. These would be the boxes in the principle...

• I tried constructing the three sets out of a given random choice of subsets: Say ${A_1,A_2,...,A_{2n+1}}$ are the 2n+1 subsets. Since the choice is random, we can consider that a subcollection exists, say $A,B,...,C$ such that these sets have at least one element of $S$ not in common. These would be the boxes in the principle... – MelaniesWoes Mar 25 '18 at 14:24
• @Melanies Please edit your question, by copying and then pasting your comment immediately above into your question. – Namaste Mar 25 '18 at 14:36
• My suggestion, which is one that I often forget to use myself, is to examine the problem with small n and try to see the pattern. So maybe let n=3, and then 4, and you might get a clearer view of what needs to happen in the general proof. – Squeeze my theorem Mar 25 '18 at 15:55
• Presumably, the question requires that the $2n+1$ subsets are distinct? – Alex Reinking Mar 26 '18 at 1:39
• Yes, I think that's what "random subsets" is supposed to convey... – MelaniesWoes Mar 26 '18 at 8:19

The strong pigeonhole principle states that if there are $n$ pigeons and $h$ holes, then there is a hole with at least $\left \lceil \dfrac nh \right \rceil$ pigeons.

Think of a Hasse Diagram: Let the $2n+1$ sets you select be the pigeons, and let your holes be the "levels" in this diagram. That is, let the first hole be the set of subsets of $1$ element, the second hole is the set of subsets of $2$ elements, ..., the $n^{th}$ hole is the set of subsets with $n$ elements. Your $2n+1$ pigeons
must be stuffed in these $n$ holes, so there must be a hole with at least $\left \lceil \dfrac {2n+1}{n} \right\rceil=3$ pigeons. That means that three of your subsets must belong on the same level, so they cannot contain each other.

• Did not know of the generalized principle, neither of Hasse Diagrams. Thanks! – MelaniesWoes Mar 25 '18 at 14:58
• @MelaniesWoes You're welcome! – Ovi Mar 25 '18 at 14:58
• Or in other words, at least 3 sets must have the same size, and a finite set can't be a subset of a different set of the same size. – user2357112 Mar 25 '18 at 17:13
• @user2357112 Right, that's a more concise way of putting it. – Ovi Mar 25 '18 at 17:34