Let $a_1,a_2,\ldots,a_n \in (0,2n)$ be $n$ distinct integers $(n \geq 4)$. Prove that there exists a nonempty subset of the set $\{a_1,\ldots,a_n\}$ whose sum of elements is divisible by $2n$.
Since there are $n$ distinct integers in $(0,2n)$, there must be a number in $(0,n]$ and a different number in $[n,2n)$ in the set $\{a_1,\ldots,a_n\}$ or both are $n$. Can we use this to show that there exists a subset of $\{a_1,\ldots,a_n\}$ whose sum of elements is divisible by $2n$?
Best Answer
We are given $n$ non-zero elements of the (additive) group $\mathbb Z_{2n}$, and we're trying to show that some of them add up to the zero element.
This can trivially be done if we have an element together with its inverse in our collection, so we can assume that our elements are specifically $$ \pm 1, \pm 2, \ldots , \pm (n-1) , n , $$ for some choice of signs $\pm$. Since we can take negatives of all elements without changing anything, we can further assume that $n-1$ comes with a plus sign. In that case, we're done if we also have $+1$ (since $1+(n-1)+n=0$), so now the situation is that we have $$ -1, \pm 2, \pm 3 , \ldots , \pm (n-2), n-1 , n . $$ We're also home if we have $-(n-2)$ (since $-1-(n-2)+(n-1)=0$), so it suffices to consider the collection $$ -1,-2,\pm 3, \ldots , \pm (n-3), n-2, n-1, n . $$ We can continue in this style and finally arrive at the following specific scenario (for odd $n$; if $n$ is even, then a similar and in fact even easier argument works): $$ -1,-2, \ldots , -m+1, \pm m, m+1, m+2 ,\ldots , 2m-1 ; \quad\quad n=2m-1 $$ It's now very easy to produce a zero sum (with three terms) in the remaining two cases (the two possible signs of $m$).