# Sets of size at least $k$ with intersection of size at most $1$ cool problem.

At the OMM School every student goes to at least $k$ classes and two classes have at most $1$ student in common. Prove there is a set of $k$ classes where all of those classes have the same amount of students.

Thank you very much for reading. I have been having trouble finding ways to combine both of the requirements. I have tried looking at the students as sets of classes, classes as sets of students. I tried seeing it as several graphs to no avail. I also tried induction, but I think if it works we need a non-straightforward hypothesis.

Thank you very much in advance

Regards.

• You have to assume that there is at least one student (or at least one non-empty class), otherwise the claim is false. Oct 17, 2014 at 3:48
• haha, why do grown ups have a tendency of saying that? Oct 17, 2014 at 3:52

This is a simple application of the pigeonhole principle. Let the degree of a class be the number of students it has. Suppose there are $n$ non-empty classes (note that $n \geq k$ assuming there is at least one student). We show below that the degree of a class is at most $(n-1)/(k-1)$. By the pigeonhole principle, some degree is attained by $n/[(n-1)/(k-1)] > k-1$ non-empty classes.
It remains to upper bound the degree of a class. Consider some class $C$ having students $s_1,\ldots,s_\ell$. Each student $s_i$ belongs to at least $k-1$ other classes, and these are disjoint among students (otherwise there will be two classes having two students in common). We conclude that $(k-1)\ell\leq n-1$.
• I considered the easier case in which $k=2$ and each student belongs to exactly two classes. You can now form a graph of classes in which any two are connected if they share an edge. We now have to show that two vertices in this graph have the same degree, a classical fact which follows from the pigeonhole principle. Given this proof it is pretty easy to solve the more general problem. Oct 17, 2014 at 3:58