# $11$ students have formed $5$ study groups. How to find 2 students $A$ and $B$ such that every study group which includes $A$ also includes $B$?

Eleven students have formed five study groups in a summer camp . Prove that two students can be found say $$A$$ qnd $$B$$ , such that every study group which includes student $$A$$ also includes student $$B$$. The solution given in the book is as follows:

We can number the study groups with numbers $${1,2,3,4,5}$$.Then instead of considering each student him or herself, we can consider the sef of numbers belonging to the study group he or she part of . We solve the problem by dividing $$32$$ subsets into $$10$$ collections such thaf if two subsets are chosen from ghis collection , one of them contains the other . The following is such a collection : [$$\phi$$,{1},{1,3},{1,2,4},{1,2,3,4},{1,2,3,4,5}], [{2},{2,5},{1,2,5},{1,2,3,5}], [{3},{1,3},{1,3,4},{1,3,4,5}] [{4},{1,4},{1,2,4},{1,2,4,5}] [{5},{1,5},{1,3,5}], [{2,4},{2,4,5},{2,3,4,5}], [{3,4},{3,4,5}], [{3,5},{2,3,5}], [{4,5},{1,4,5}] [{2,3},{2,3,4}].

Well, can someone please tell how to construct such a collection ....I mean how to arrive at such a collection so that it gives us the required result...is thee a way? I mean what is the idea behind it?I am not quite getting the idea behind it...I mean the way to construct such a collection of subsets

• Don’t mangle your title just to fit the whole question there. Hint: The title does not need to be the whole question, and the body of the question should contain the whole question. Commented Apr 14, 2022 at 3:57
• @ThomasAndrews Thanks for sharing! I thought it might have created some confusion so I chose to post in that way....
– user992622
Commented Apr 14, 2022 at 4:08
• No, edit it. It reads horribly. Commented Apr 14, 2022 at 4:20
• @ThomasAndrews Do u think that'll be alright? If i do it... wont it confuse the readers ? I mean its alright anyways....besides I am looking for an answer....
– user992622
Commented Apr 14, 2022 at 4:22
• @ThomasAndrews I have already edited it...I think the issue is now resolved....
– user992622
Commented Apr 14, 2022 at 4:44

We can think of every student as a subset of $$S= \{1,2,3,4,5\}$$ and suppose that for each two $$A$$ and $$B$$ there is an $$x\in S$$ that is in $$A$$ and not in $$B$$ and $$y\in S$$ that is in $$B$$ and not in $$A$$, i.e. $$A$$ and $$B$$ does not contain the other. Then by Sperner theorem we can have at most $${5\choose 2}=10$$ such sets. A contradiction.
• that's a nice solution but can u please explain that when u say that the no. of such sets possible at maximum is $10$ ...well but here we are partitioning into $5$ groups so where do u get the contradiction?