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.
Like in previous exercises, let’s follow the principle and define the boxes and the objects.
Let’s enumerate the first eight positive integers: 1, 2, 3, 4, 5, 6, 7, 8.
Now, let’s create groups of two integers that the sum is 9.
- (1,8)
- (2,7)
- (3,6)
- (4,5)
These are the boxes; we have 4 boxes that add to 9.
Now, if we choose five integers (from the first 8 positive integers), and put them into the box that corresponds with the number we can conclude the following:
By the pigeonhole, if we choose five from the first 8 integers, at least the sum of two of them will 9.
In other words, if you place 5 integers (from 1 to 8) in the corresponding box enumerated above (1 goes to box 1, 7 goes to box 2, 5 goes to box 4, …), then at least 1 box will have two integers. Because the boxes are designed to add 9, then at least two of the chosen 5 integers will add to 9.
Is the conclusion in part (a) true if four integers are selected rather than five?
The answer is no.
We can use a counter example to justify our answer.
If you choose 1, 2, 3 and 4; there is no pair that the sum equals 9.
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?
- Show that if there are 30 students in a class, then at least two have last names that begin with the same letter
- 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