Show that if five integers are selected from the set 1 2 3 7

Show that if five integers are selected from the set {1, 2, 3, ...,7, 8}, then at least one pair of the integers selected has a sum of 9.

Solution

Partition the set A into 4 subsets:

          {1, 8}, {2, 7}, {3, 6}, and {4, 5},

each consisting of two integers whose sum is 9. If 5 integers are selected from A, then by the Pigeonhole Principle at least two must be from the same subset. But then the sum of these two integers is 9