7
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ You have to assume that there is at least one student (or at least one non-empty class), otherwise the claim is false. $\endgroup$
    – Yuval Filmus
    Oct 17, 2014 at 3:48
  • $\begingroup$ haha, why do grown ups have a tendency of saying that? $\endgroup$
    – Asinomás
    Oct 17, 2014 at 3:52

1 Answer 1

Reset to default
1
+50
$\begingroup$

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$.

$\endgroup$
3
  • $\begingroup$ wow, how are you so good at this type of problems, it isn't the first time I've seen you do this. $\endgroup$
    – Asinomás
    Oct 17, 2014 at 3:55
  • $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Oct 17, 2014 at 3:58
  • $\begingroup$ hmm, I did that and didn't think of bounding the degrees. Sometimes I dismiss ideas on the account they don't seem "strong enough". Thanks a lot though. $\endgroup$
    – Asinomás
    Oct 17, 2014 at 4:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .