11
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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... $\endgroup$ – MelaniesWoes Mar 25 '18 at 14:24
  • 1
    $\begingroup$ @Melanies Please edit your question, by copying and then pasting your comment immediately above into your question. $\endgroup$ – Namaste Mar 25 '18 at 14:36
  • 2
    $\begingroup$ 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. $\endgroup$ – Squeeze my theorem Mar 25 '18 at 15:55
  • 1
    $\begingroup$ Presumably, the question requires that the $2n+1$ subsets are distinct? $\endgroup$ – Alex Reinking Mar 26 '18 at 1:39
  • $\begingroup$ Yes, I think that's what "random subsets" is supposed to convey... $\endgroup$ – MelaniesWoes Mar 26 '18 at 8:19
17
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Did not know of the generalized principle, neither of Hasse Diagrams. Thanks! $\endgroup$ – MelaniesWoes Mar 25 '18 at 14:58
  • 1
    $\begingroup$ @MelaniesWoes You're welcome! $\endgroup$ – Ovi Mar 25 '18 at 14:58
  • 4
    $\begingroup$ 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. $\endgroup$ – user2357112 Mar 25 '18 at 17:13
  • 1
    $\begingroup$ @user2357112 Right, that's a more concise way of putting it. $\endgroup$ – Ovi Mar 25 '18 at 17:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.