# Pick $n+2$ integers from a set of $2n-1$. Prove that the sum of $2$ of the selected integers will be equal to one of the selected numbers

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

Hint: Let the largest number selected be $$k$$. How many pairs sum up to $$k$$?

There are $$\lfloor \frac{k}{2} \rfloor$$ pairs that 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.

• Are you sure about that because the second part of the question is that with n+1 items the sum won't be in the subset and i should find that subset.. – Paradox Nov 30 '19 at 19:52
• Can you find such a subset for any $n$? I suspect that the problem was meant to be $2n+1$. – Calvin Lin Nov 30 '19 at 19:55
• The question is from a book ,unfortunetly is not in English so i can't tell you which one :( . It's a university book. They use that book for years so i think if it was a typo they should have find it out by now . I am not 100% sure though – Paradox Nov 30 '19 at 19:59
• Is the second part also written in the book? Or are you just trying to find the strongest bound? – Calvin Lin Nov 30 '19 at 20:14
• It is i included a screenshot but as i said everything will be Greek to you because it's in Greek imgur.com/a/WvprxLt – Paradox Nov 30 '19 at 20:27