A subset whose sum of elements is divisible by $n$ 
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$?
 A: 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$).
A: You can also do it with a slightly fancy pigeonholing. Let's prove first that given $n-1$ distinct numbers in $(0,2n)$, we can find several of them whose sum is divisible by $n$. Arrange them in some order and consider $n-1$ numbers $a_1, a_1+a_2,\dots, a_1+\dots+a_{n-1}$. If one of them is divisible by $n$, we are done. If two of them have the same remainder modulo $n$, we are done. Thus, we must have all possible non-zero remainders occurring exactly once, which forces us to have a very particular remainder of the sum $(n-1)a_1+(n-2)a_2+\dots+a_n$. However, if we swap two adjacent numbers, this remainder changes by their difference, so if we have 2 different remainders among $a_j$, we can easily avoid this scenario. Otherwise all numbers have the same remainder, which forces the largest one be at least $1+n(n-2)>2n$ if $n\ge 4$.
Now consider 2 cases:
1) $n$ is in the set. Then choose the subset of other numbers with sum divisible by $n$ and, if it fails to be divisible by $2n$, join $n$ to it.
2) $n$ is not there. Then there is a pair $k,2n-k$ for some $k\in[1,n-1]$ and there is nothing to do. 
