Problem 2
Students in a class form groups, each of which contains exactly three members, such that any two distinct groups have at most one member in common. Prove that, when the class size is 46, there is a set of 10 students in which no group is properly contained.
Step 2 of 5: Assume the contrary
Detailed analysis
Assume s≤9. For every student v outside S, maximality says that adding v would create a whole group, so some group consists of v and two students of S. Each pair of students of S belongs to at most one group, by the intersection hypothesis. Hence at most binomial(s,2)≤36 outside students can be accounted for this way.