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

Related material
Read more...

  • Pigeonhole Principle and Extensions
  • Twenty five boys and twenty five girls
  • Pigeonhole in Chess Training
  • Married Couples at a Party
  • Jumping Isn't Everything
  • Zeros and Nines
  • Teams In a Tournament
  • Divisibility of a Repunit
  • Pigeonhole in Clubs

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

    Copyright © 1996-2018 Alexander Bogomolny

     64686463