3
$\begingroup$

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...

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ If this is a hint, then what's the answer? :) $\endgroup$ – Amit Kumar Gupta Feb 26 '13 at 6:15
  • $\begingroup$ 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. $\endgroup$ – André Nicolas Feb 26 '13 at 6:20
  • $\begingroup$ Thanks a bunch! You're right - I'm having trouble identifying the "boxes", and consequently having trouble applying the principle. $\endgroup$ – user64025 Feb 26 '13 at 6:30

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.