3
$\begingroup$

Here is a statement I encounter: For any positive integer $n$, and $2n-1$ integers, there must exist $n$ integers in it such that the sum of these $n$ integers is a multiple of $n$.

I have no ideas how to prove this. If I have proved that the statement is true when $n$ is a prime number, how do I prove the case when $n$ is an arbitrary positive integer? Or could anybody give some useful hints about the proof of the statement?

Thank you very much!

1 Answers 1

7

This is the Erdős–Ginzburg–Ziv theorem. There are many proofs and they all start by reducing to the case that $n$ is prime. Since you have already taken care of that you just need the observation that if the theorem holds for $n$ and $m$, then it holds for $nm$.

Take $2nm-1$ integers and pick $2n-1$ of them. Our hypothesis says we can find a set $S_1$ of $n$ integers among these so that $|S_1|=\sum_{x\in S_1} x\equiv 0\pmod{n}$. After removing all the elements of $S_1$ we are left with $(2m-1)n-1$ elements and we repeat the procedure. Obviously this goes only as far as $S_{2m-1}$, but this is enough since out of the $2m-1$ numbers $\{\frac{|S_1|}{n},\dots,\frac{|S_{2m-1}|}{n}\}$ there exist $m$ with sum $0\pmod{m}$, and the union of the corresponding $S_i$'s is a set of $mn$ elements with sum divisible by $mn$.