Find a subset such that its sum is divisible by $n$

Question

It is said that the following proposition is true.

$\forall S \subset \mathbb{Z}, |S| = 2n-1.\ \exists A \subset S, |A| = n$ which satisfies $$ n \ | \ \sum_{a \in A}a. $$ Could someone gives a proof or some infomation about this? Thx.

Answer 1

It is Erdős–Ginzburg–Ziv theorem. The standard proof is induction on number of prime divisors of $n$.

If $n$ is prime, let $0\leqslant x_1\leqslant \dots \leqslant x_{2n-1}\leqslant n-1$ be elements of $S$ (we may think so of course). If $x_i=x_{n-1+i}$ for some index $i\in \{1,2,\dots,n-1\}$, we take $A=\{x_i,\dots,x_{n-1+i}\}$. If not, denote sets $U_i:=\{x_i,x_{n-1+i}\}$ for $i=1,\dots,n-1$, $U_0:=\{x_{2n-1}\}$. I claim that $|U_0+\dots+U_k|\geqslant k+1$ for all $k=0,\dots, n-1$ (set addition is modulo $n$), for $k=n-1$ this is implies the claim, since $0\in U_0+\dots+U_{n-1}$ is enough for our goal. This is easy induction. For $k=0$ the claim is clear. If it holds for $k-1$, but does not hold for $k$, then the sets $A=U_0+\dots+U_{k-1}+x_k$ and $B=U_0+\dots+U_{k-1}+x_{n-1+k}$ each have exactly $k$ elements and coincide. But $B=A+(x_{n-1+k}-x_k)$, and, since $n$ is prime, there is no subset $A$ of residues mod $n$, which has $k$ elements and coincides with its translate $A+t$, $t\ne 0$.

(Remark: this step is often proved using Cauchy-Davenport theorem, but you see that we need only an easy particular case of Cauchy-Davenport.)

Now induction step. If $n=ab$, $a>1$, $b>1$ and both for $a$ and for $b$ the claim holds, then we may find $a$ elements with sum divisible by $a$ out of any $2a-1$ elements. Do this, remove $a$ these elements and proceed. We may do this $2b-1$ times, i.e. there exist $2b-1$ disjoint subsets $A_1,\dots,A_{2b-1}$, $|A_i|=a$, $\sum_{a\in A_i}a=ak_i$. Apply the claim for $k_1,\dots,k_{2b-1}$.

Remark: almost the same argument works in any Abelian group of order $n$.