2
$\begingroup$

if we have n + 2 natural numbers there are always 2 whose sum or difference is a multiple of 2n + 1. I tried to use the pigeonhole principle with remainder technique. If the numbers are divisible by 2n+1, then we have 2n possible remainders. However, the n+2 numbers will be matching 2n remainders and n+2<2n, so I am stuck. Any help is appreciated!

$\endgroup$
5
$\begingroup$

There are $2n+1$ residue classes $\pmod {2n+1}$. If two of your numbers are in the same residue class, then (by definition) their difference is divisible by $2n+1$, so let's suppose that they occupy $n+2$ distinct residue classes.

Now remark that we can divide the classes into pairs that add to a multiple of $2n+1$, namely $(1,2n),(2,2n-1),\cdots, (n,n+1)$ with $0$ left unpaired. We note that there are $n$ pairs. Even if $0$ is one of your choices, we would still have to make $n+1$ choices from those pairs. by the pigeon hole principle, therefore, if you have $n+2$ choices you must have chosen two from the same pair, and we are done.

$\endgroup$
  • $\begingroup$ beautifully simple. (+1) $\endgroup$ – Karl Feb 8 '17 at 20:51
0
$\begingroup$

Since you consider the sum and the difference on those natural numbers, it boils down to considering only the differnce on relative numbers (where each non-zero natural number has been duplicated as a negative one). Since $0$ could be among your $n+2$ numbers, by duplicating non-zero numbers, you obtain a set of at least $2n+3$ relative numbers. You want two of them to fall in the same residue class among $2n+1$. Pigeons cannot fit.

Note that with $n+1$ natural numbers, when the $0$ is used, you may obtain $2n+1$ relative numbers and they may live in pairwise distinct residue classes. Pigeons can sleep comfortably then.

$\endgroup$

Your Answer

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