How many numbers must be selected from the set 1 3 5 7 9 11

How many numbers must be selected from the set {1, 3, 5, 7, 9, 11, 13, 15} to guarantee that at least one pair of these numbers add up to 16?

Solution

We can apply the pigeonhole principle by grouping the numbers cleverly into pairs (subsets) that add up to 16, namely

{ 1; 15} , { 3; 13} , {5 ; 11}, and { 7; 9 } .

If we choose five numbers from the set { 1; 3; 5; 7 ; 9; 11; 13; 15} and

then at least two of them must fall within the same subset since there are only four subsets. Two numbers in the same subset are the desired pair that add up to 16. We also need to point out the choosing four numbers is not enough, since we could choose { 1; 3; 5; 7 },

and no pair of them add up to more than 12.