I want to prove that if we select $n+2$ integers from a set of $\{1, 2, 3,…, 2n−1\}$, then the sum of $2$ of the selected will be equal to one of the numbers we selected.
I understand that i can solve this with Pigeonhole Principle but i don't know how.
I also want to find a subset of $\{1, 2, 3,…, 2n−1\}$ with $n+1$ items which won't have that ability (if we add $2$ of those $n+1$ items the result won't be in subset). I guess that will be easy if i prove the first part but right know i don't understand how should i proceed.
Any help would be greatly appreciated
Best Answer
Hint: Let the largest number selected be $k$. How many pairs sum up to $k$?
Even with $n+1$ items out of $\{2n-1\}$, you can still find a pair that sum, via the above argument:
Suppose we picked $n+1$ items out of $\{2n-1\}$.
Let $ k \leq 2n-1$ be the largest element.
Consider the $\lfloor \frac{k}{k}\rfloor \leq n-1$ pairs $(1, k-1), (2, k-2), \ldots (\lfloor \frac{k}{k}\rfloor, \lceil \frac{k}{k}\rceil)$.
Since we picked $n$ items out of these, by the Pigeonhole principle, some hole contains 2 pigeons, whose sum is $k$.
Conversely, the $n$ items $\{n-1, n, \ldots, 2n-2\}$ do not have any pair that sum to another element. The set $\{n, \ldots, 2n-2, 2n-1\}$ also works.