# Want to Know if There's a Way to Solve This Problem Using Combinations?

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

• Welcome to MSE. It will be more likely that you will get an answer if you show us that you made an effort. – José Carlos Santos May 1 '18 at 13:40
• 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. – 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.