If we have $n + 2$ natural numbers there are always $2$ whose sum or difference is a multiple of $2n + 1.$

Question

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\lt2n,$ so I am stuck. Any help is appreciated!

Answer 1

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.

Answer 2

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.