Prove that if n + 1 distinct numbers are selected from 1 to 2n - 1, then there is always a number in selected ones that is sum of two other selected

Question

It looks to me that this is Pigeonhole related question but can't come up with the proof. I tried this: Group numbers in pairs such that sum of pairs equals to 2n - 1. If 2n - 1 is selected then by Pigeonhole principle there will be a pair that is selected too. But what if 2n -1 is not selected?

Answer 1

I think that you can extend the argument you made a little bit. You showed that the condition is satisfied if $2n - 1$ is selected. What if the biggest number selected is $2n - 2$? Now we have can divide the rest of the numbers into pairs that add $2n - 2$ (note that $n - 1$ is alone, but there are still $n - 2$ groups and we have to select more than one number from some group). This argument can continue if $2n - 3$ is the greatest, $2n - 4$ is the greatest, and so on. Hope this helps!