A teacher provides four special lessons, one each in Maths, Music, English and Science, for some of the children in her class. For the students in these special lessons: • there are exactly 3 children in each lesson. • each pair of students attends at least one special lesson together. What is the largest number of students who can attend these special lessons?
Can someone help me solve this problem?
On
With six kids, there are $\binom62=15$ different pairs. Each lesson hosts $\binom32=3$ pairs, and there are only four lessons, so at least three pairs will never meet. Therefore, six is too many.
Can you make it happen with five? Try to build a complete graph on five vertices, i.e., a pentagon with a star inscribed, out of four triangles, overlapping allowed (indeed, necessary).
Consider the number of possible pairs in the lessons, each class has $3$ pairs and the there are $4$ classes, so that makes $12$ possible pairs.
If there are $5$ students there are $10$ pairs, if there are $6$ students there are $15$ pairs (too many!), so the largest number of students is possibly $5$, now can all $10$ pairs be realised in the four classes ...
The answer is yes ...