Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

1 Answer

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|improve this answer
3  
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
add comment

Your Answer

 
discard

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.