Inevitable Zero-Sum numbers in a set

Prove that for any set of $2n+3$ integers from the interval $[-2n-1,2n+1]$ there is a triple $(x,y,z)$ such that $x+y+z=0$.

Example : Choose $5$ number from $\{-3,-2,-1,0,1,2,3\}$ there are $x,y,z$ with $x+y+z=0$.

Solution 1:

Here is the proof several cases, though Case 0 is trivial, Case 1 and Case 3 are similar to each other, and Case 2 and Case 4 are also similar to each other (so we might say that there are only two important cases).

Case 0. If $0$ is among the chosen numbers, then use that there is non-zero $x$ with both $x$ and $-x$ among the chosen numbers, so then the sum $x+(-x)+0=0$ works. Such an $x$ exists since otherwise the absolute value function would be an injective map from the set of $(2n+2)$-many non-zero chosen numbers into the interval $[1,..,2n+1]$ which is impossible.

In all remaining cases, I will assume that $0$ is not chosen.

Case 1. Neither $-2n-1$ nor $2n+1$ are among the chosen numbers. Then we could also remove $\pm 2n$, thus removing at most two chosen numbers, and restrict our attention to the interval $[−2n+1,..,2n−1]=[−2(n−1)−1,..,2(n−1)+1]$, and in it we have at least $2n+3−2=2(n−1)+3$ chosen numbers, and apply induction hypothesis (where the context of a proof by induction ought to be clear, the base case being $n=0$, choosing three integers from the interval $[-1,0,1]$, then clearly the choice is unique and $-1+0+1=0$). We are done in this case too.

So we may assume without loss of generality that either $-2n-1$,or $2n+1$, or both are among the chosen numbers. After replacing each number with its opposite (if necessary) we may assume (in all remaining cases) that $2n+1$ is one of the chosen numbers.

Case 2. Both $-2n-1$ and $2n+1$ are among the chosen numbers. It is better to illustrate this case with an example first. Say $n=3$ so we consider the interval $[-7,..,7]$ and both $-7$ and $7$ are among the chosen numbers. Then (assuming the statement we are trying to prove were false) it is not possible that both $-6$ and $-1$ are chosen (since then $-6+(-1)+7=0$). More generally there could be at most one chosen number in each pair $\{-6,-1\}$, $\{-5,-2\}$, $\{-4,-3\}$, $\{3,4\}$, $\{2,5\}$, $\{1,6\}$. Thus, there could be at most three chosen numbers in $[-6,..,-1]$ and at most three in $[1,..,6]$, and these numbers together with $-7$ and $7$ make at most $8$ chosen numbers, but the chosen numbers were supposed to be $2n+3=9$, a contradiction. Clearly this works in general: If both $-2n-1$ and $2n+1$ are among the chosen numbers then there are at most $n$-many chosen numbers in $[-2n,..,-1]$, at most $n$-many in $[1,..,2n]$, and this would make at most $2n+2$ total, a contradiction.

So, in all remaining cases we may assume that $2n+1$ is chosen, but $-2n-1$ is not.

Case 3. At most one of the numbers $-2n$ and $2n$ is chosen. This is treated very much like Case 1: Restricting our attention to the interval $[−2(n−1)−1,..,2(n−1)+1]$, where we have at least $2(n−1)+3$ chosen numbers, and apply induction hypothesis.

Case 4. Both $-2n$ and $2n$ are chosen. This is treated similar to Case 2. So, $2n+1$ and $\pm 2n$ are chosen. The number $n$ may be chosen. At most $n$-many numbers in $[-2n,..,-1]$ may be chosen, and this includes the chosen number $-2n$. At most $(n-1)$-many numbers may be chosen in $[1,..,n-1]\cup[n+1,..,2n-1]$. This makes total of at most $3+1+n-1+n-1=(2n+2)$-many numbers, a contradiction, which completes the proof. (The last count one more time in a slightly different manner: The numbers $2n+1$ and $2n$ are chosen, and $n$ may be chosen. Then at most $n$-many in $[-2n,..,-1]$ (including the number $-2n$) and at most $(n-1)$-many in $[1,..,n-1]\cup[n+1,..,2n-1]$, this makes $3+n+n-1=2n+2$ numbers at most.)

Note. The assumption that the endpoints are odd is important. Indeed we may pick four numbers $\{-2,-1,1,2\}$ in $[-2,..,2]$ with no triple among them that sums up to $0$. Similarly we may pick six numbers $\{-4,-3,-2,2,3,4\}$ in $[-4,..,4]$ with no zero-sum triple. This seems to generalize, $[-2n,..,-n]\cup[n,..,2n]$ are $(2n+2)$-many numbers in $[-2n,..,2n]$ with no zero-sum triple.