For this particular exercise, let’s refresh the pigeonhole principle.
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.
As in previous counting exercises examples, we will express the problem in the same way that a definition (the pigeonhole principle in this case) is expressed.
Let:
- k=5 be a positive integer, representing the 5 days of a week (without the weekend days). These are the 5 boxes.
- k+1 be the number of classes, 6 in this case. These are the objects.
Then, by the pigeonhole principle, at least two classes have a meeting on the same day of the week.
In other words, there is at least 1 box (1 day of the week) that contain two or more objects (classes meetings).
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 if there are 30 students in a class, then at least two have last names that begin with the same letter
