Question

Let A = {1, 2, 3, 4, 5, 6, 7, 8, 9}. n distinct integers will be chosen from A. How big does n have to be

Answer 1

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.