# Prove that it's possible to find two students in the same group

(Adapted) (Mathematical Circles) Eleven students formed five study groups. Prove that we can find two students, say A and B, that every study group that includes student A also includes student B

One solution is to name every group as $1,\dots ,5$ and then say that every student must be in a subset of $\{1,\dots, 5\}$. Then rearrange these subsets in other sets. Say that set $A$ is one of those other sets. $A$ is such that if two students are in the same set, they must be in the same groups (every set element is a subset of a element of $A$). Example: $A = \{ \{1\}, \{1,2\}, \{1,2,3\}, \dots\}$. This way, we can apply the pidgeonhole principle and show that at least two students are in the same $A$.

However, this solution is not very intuitive. Is there any other solution?

• To be clear, a group that includes student $B$ but not student $A$ would not disqualify the pairing? – Joffan Jan 19 '17 at 19:08
• @Joffan iff all groups for all students A and B – Lucas Henrique Jan 20 '17 at 18:50
• Let me ask again a different way. If we have such a pairing $A$ and $B$ as per the question, is it possible that there is a group that contains student $B$ but does not contain student $A$? – Joffan Jan 20 '17 at 18:56
• There is. But only if we're talking about students A, ..., (student 11). There might be students with the property you said, but there are at least two that are in the same group – Lucas Henrique Jan 21 '17 at 2:36
• My motivation is that it is relatively easy to make sure that no two students are always together - that is, they are always both in a group or both out of it. You can do that with only four groups. So I was trying to find out how the one-way relation works, exactly. – Joffan Jan 21 '17 at 3:11

So we have $11$ sets $A_1,...,A_{11}$ which are subsets of the set $S= \{1,2,3,4,5\}$. ($A_i$ represents i-th student and $j\in A_i$ iff the student $i$ is in the $j$-th group). We have to prove that there exist $A_m=:A$ and $A_n=:B$ such that if $k\in A$ then $k\in B$ i.e. $A\subset B$.
Say there is no such pair. But then we have an antichain $A_1,...,A_{11}$ which wide is $11$. But this is impossible by Sperner theorem which tell's us that in $S$ we have an antichain which is wide at most ${5\choose 2} = 10$. A contradiction.
I would look at it as a function $f$ from $[[11]]$ to $P([[5]])$ such that for all $a,b \in [[11]]$ $f(a) \not \subset f(b)$. Then with Dilworth's theorem you can see that there are at most $\binom{5}{3}=10$ anti-chains.