Students in Classes

Suppose 70 students take between them 11 different classes. 15 is the maximum class size. Show that there are at least 3 classes attended by at least 5 students each.

Solution


|Contact| |Front page| |Contents| |Up|

Copyright © 1996-2018 Alexander Bogomolny

Suppose 70 students take between them 11 different classes. 15 is the maximum class size. Show that there are at least 3 classes attended by at least 5 students each.

Having 70 students attending 11 classes lets us apply the pigeonhole right away to claim there is a class attended by at least ⌊70/11⌋ + 1 = 7 students. We are looking for three classes with attendance of at least 5 students. The one we found with at least 7 students clearly fits the bill. Call it class A.

In class A, there are at most 15 students. The remaining 55 ones take between them 10 remaining classes. As before, there is a class, call it B, with at least ⌊55/10⌋ + 1 = 6 students.

There are at most 15 students in class B. The remaining 40 (= 55 - 15) take between them the remaining 9 classes. Thus, there is a class, say C, with at least ⌊40/9⌋ + 1 = 5 students, and we are done.

References

  1. W. D, Wallis, J. C. George, Introduction to Combinatorics, CRC, 2010, p. 49

[an error occurred while processing this directive]

|Contact| |Front page| |Contents| |Up|

Copyright © 1996-2018 Alexander Bogomolny
[an error occurred while processing this directive]
[an error occurred while processing this directive]