1
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$ Commented Apr 14, 2022 at 3:57
  • $\begingroup$ @ThomasAndrews Thanks for sharing! I thought it might have created some confusion so I chose to post in that way.... $\endgroup$
    – user992622
    Commented Apr 14, 2022 at 4:08
  • $\begingroup$ No, edit it. It reads horribly. $\endgroup$ Commented Apr 14, 2022 at 4:20
  • $\begingroup$ @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.... $\endgroup$
    – user992622
    Commented Apr 14, 2022 at 4:22
  • $\begingroup$ @ThomasAndrews I have already edited it...I think the issue is now resolved.... $\endgroup$
    – user992622
    Commented Apr 14, 2022 at 4:44

1 Answer 1

1
$\begingroup$

Here is alternative solution to your problem.

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.

And you don't need to construct anything.

$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$
    – user992622
    Commented Apr 15, 2022 at 9:33

You must log in to answer this question.