4
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.