Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let n be greater or to 1, and let S be an (n+1)-subset of [2n]. Prove that there exist two numbers in S whose sum is 2n+1.

I know I have to use the pigeonhole principle - no idea how to start...

share|cite|improve this question

Consider the $n$ pairs $\{1,2n\}$, $\{2,2n-1\}$, $\{3,2n-2\}$, and so on up to $\{n,n+1\}$. The two numbers in each pair add up to $2n+1$.

If we choose $n+1$ numbers, then they cannot all belong to different pairs.

You can reword this in terms of pigeons. The pair $\{1,2n\}$ are a couple, with their own pigeonhole, as are $\{2,2n-1\}$, and so on up to $\{n,n+1\}$. If there are $n+1$ pigeons currently in the pigeonholes that are their homes, then some couple must be at home.

share|cite|improve this answer
If this is a hint, then what's the answer? :) – Amit Kumar Gupta Feb 26 '13 at 6:15
Now it is even longer, and I have removed the hint label. Actually, it was a hint before, because they are probably expected to identify the pigeonholes, and students often have trouble with that. – André Nicolas Feb 26 '13 at 6:20
Thanks a bunch! You're right - I'm having trouble identifying the "boxes", and consequently having trouble applying the principle. – user64025 Feb 26 '13 at 6:30

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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