Is there a way to solve this problem using combinations? I've been getting to the given correct answer using trial and error but I want to know if there's a way using something related to combinations or permutations? Here's the problem:

A teacher is providing her students with 4 special lessons. (a) Each lesson has exactly 3 participants, (b) Any two students must attend at least one special lesson together. According to these two conditions, what is the maximum number of students who can join these special lessons?

Thank you

  • $\begingroup$ Welcome to MSE. It will be more likely that you will get an answer if you show us that you made an effort. $\endgroup$ – José Carlos Santos May 1 '18 at 13:40
  • $\begingroup$ Hi! As this was my first time posting I didn't really know that it would be preferred that I attempt to show a solution. My issue with this problem is that I couldn't seem to think of a way to try and find a solution using what I knew about combinations and permutations, as this was the first time I encountered something where "N" or the total number of objects/students wasn't given. Thanks for your suggestion anyway. $\endgroup$ – RC Wong May 3 '18 at 6:49

Suppose there are $n$ students attending the lessons. This means there are $\binom{n}2$ pairs which need to attend a lesson together. Since every lesson takes care of at most $\binom32=3$ pairs of students, and there are four lessons, we must have $$ \binom{n}2\le 3\cdot 4=12 $$ This immediately implies $n\le 5$, because $\binom{6}2=15>12$.

This does not prove that $5$ students is sufficient, but it gives you a place to start looking. Namely, try to see if $5$ students is possible, and if you suspect it is not, then come up with a proof of this. In general, solving "combinatorial design" problems like these are very hard, so you cannot expect it to be entirely solved using elementary techniques like combinations.

  • $\begingroup$ Hi Mike, thanks for this suggested solution. Based on the answer key, the answer was indeed 5. I do begin to understand the method of solving this based on your suggested solution. I guess I understand now that while this may be related in some way to combinations, there's no way to use any simple combinatorial method to reach the solution. Thank you again for your time. $\endgroup$ – RC Wong May 3 '18 at 6:50
  • $\begingroup$ Happy to help, @RCWong, best wishes $\endgroup$ – Mike Earnest May 3 '18 at 14:32

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.