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

Question

(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?

Answer 1

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.

Answer 2

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.