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. (Pigeonhole)

Question

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.

Answer 1

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$.