Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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!
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$.
