Show that any subset of $\{1, 2, 3, ..., 200\}$ having more than $100$ members must contain at least one pair of integers which add to $201$.

Question

Show that any subset of $\{1, 2, 3, ..., 200\}$ having more than $100$ members must contain at least one pair of integers which add to $201$.

I think it is doable using the Pigeonhole Principle.

Answer 1

Consider the subset {$1,2,3,...,100$}. No two integers from this set sum to $201$. However, the very next integer you include in this set gives you the smallest subset with more than $100$ integers in it where two of the integers sum to $201$. Any other subset of the desired size will always have two integers whose sum is $201$. Thus any subset of {$1,2,3,...,200$} that contains more than $100$ integers must contain at least one pair of integers whose sum is $201$.

Answer 2

Hint: think about the pairs that add to $201$. How many such pairs are there?