thank you Use the Pigeonhole Principle to prove that if A is

thank you!

Use the Pigeonhole Principle to prove that, if A is a subset of {1, 2,..., 2016} with at least 1009 elements, then there are two elements of A which add up exactly to 2017.

Solution

We can split the set: {1,2,....,2016} into two sets:

X={1,2,...,1007} and Y={1008,1009,...,2016}

If you select any two elements from X the sum can take maximum value: 1007+1006=2013

If you take any two elements from X smallest sum is:1008+1009=2017

Let, X and Y be the two holes. We need to select total of 1009 so 2 have to be selected from Y

Hence at least two elements ahve sum:2017