Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
add comment

1 Answer

up vote 7 down vote accepted

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

share|improve this answer
    
Ok,great! Thank you. –  wxu Aug 18 '11 at 6:21
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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