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.

  • $\begingroup$ 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.. $\endgroup$ – Paradox Nov 30 '19 at 19:52
  • $\begingroup$ Can you find such a subset for any $n$? I suspect that the problem was meant to be $2n+1$. $\endgroup$ – Calvin Lin Nov 30 '19 at 19:55
  • $\begingroup$ 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 $\endgroup$ – Paradox Nov 30 '19 at 19:59
  • $\begingroup$ Is the second part also written in the book? Or are you just trying to find the strongest bound? $\endgroup$ – Calvin Lin Nov 30 '19 at 20:14
  • $\begingroup$ 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 $\endgroup$ – Paradox Nov 30 '19 at 20:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.