Show that if 5 integers are selected from the first 8 positive integers, there must be a pair of these integers with a sum equal to 9.
The question calls for the use of the pigeonhole principle.
This is what I've got so far:
Divide the 8 integers into 4 groups.
Pigeons N = 5 integers
Pigeonholes k = 4 groups
⌈N/k⌉ = ⌈5/4⌉ = 2
Since it's stated that "there must be a pair of these integers with a sum equal to 9", does that mean it should be ⌈N/k⌉ = 1? I'm not quite sure how to apply the pigeonhole principle here.
Best Answer
The idea here is to construct your subsets so that if you select both members of that subset you will obtain a sum of $9$.
In this case, we can construct the subsets $\{1, 8\}, \{2, 7\}, \{3, 6\}, \{4, 5\}$. Since we are selecting five elements and there are only four subsets, we must select $$\left\lceil \frac{5}{4}\right\rceil = 2$$ members from at least one of these subsets. Since the sum of the elements in each subset is $9$, we are guaranteed to select a pair of integers whose sum is $9$.