Let’s start with the following definition.
THE PIGEONHOLE PRINCIPLE: “If k is a positive integer and k + 1 or more objects are placed into k boxes, then there is at least one box containing two or more of the objects.” Discrete Mathematics and its applications by Rosen.
The number of available letters in the English alphabet is 26.
So, let k=26 be the number of boxes and the 30 the number of objects (students) that we are going to put inside the boxes.
Then, by the pigeonhole principle, at least one box (last name first letter) has two or more objects (a student last name).
Another possible solution to this problem is to use the generalized pigeonhole principle.
THE GENERALIZED PIGEONHOLE PRINCIPLE: “If N objects are placed into k boxes, then there is at least one box containing at least ⌈N/k⌉ objects.” Discrete Mathematics and its applications by Rosen.
In this case, we will say that if 30 student-last-names are placed in 26 boxes, then at least one box contains ⌈30/26⌉=2 student-last-names, by the generalized pigeonhole principle.
Related exercises:
- What is the minimum number of students, each of whom comes from one of the 50 states, who must be enrolled in a university to guarantee that there are at least 100 who come from the same state?
- (a) Show that if five integers are selected from the first eight positive integers, there must be a pair of these integers with a sum equal to 9. Is the conclusion in part (a) true if four integers are selected rather than five?
- Show that among any group of five (not necessarily consecutive) integers, there are two with the same remainder when divided by 4
- Show that in any set of six classes, each meeting regularly once a week on a particular day of the week, there must be two that meet on the same day, assuming that no classes are held on weekends
