The theorem of Erdös-Ginzburg-Ziv says: Let $ S$ be a set of $ 2n - 1$ integers (we can allow them to occure more than once in the set). Then there is some $ n$ element subset of $ S$ having sum divisible by $ n$. The whole theorem is proven by showing that if it holds for $ n = a,b$, then it holds for $ n = ab$. By this it's reduced to primes, where one can show it on various ways, e.g. using the theorem of Chevalley-Warning or alternatively using that if Cauchy-Davenport. If you want, I can post a full proof. This one is $ n = 6$: There is no problem to check it for $ n = 2,3$ by hand, then one only needs to care about the proof of multiplicativity for this case here.

I remember that Arne (from ML) had a nice direct solution for this (short and no casework or anything), but I can't remember it. It was on Kalva but disappeared when the British MO was taken off.

This was Arne's proof. Arne wrote: Lemma 1: among any three integers, two integers can be found having an even sum. Lemma 2: among any five integers, two integers can be found having a sum which is divisible by 3. (Proof: almost trivial, pigeonhole principe.) Now, given $ a_{1},a_{2},a_{3},\,\cdots,a_{11}$, we can assume without loss of generality that $ b_{1}= a_{1}+a_{2}$ is even, by Lemma 1. Also, we can suppose that $ b_{2}= a_{3}+a_{4}$ is even, ..., and that $ b_{5}= a_{9}+a_{10}$ is even. Among the five integers $ b_{1},b_{2},\,\cdots,b_{5}$, three can be found having a sum which is a multiple of 3, by Lemma 2. But the sum of these $ b_{i}$ is equal to the sum of six of the numbers $ a_{i}$, so we have found six numbers among the given ones which have their sum divisible by 6. We can conclude that such a set cannot exist. Maybe this proof can be generalized. @ZeTaX: Yes, it would be nice if you could post a full proof.

Sorry, haven't seen your response. In fact, Arne's proof is the one I mentioned above. Here a proof of the general thing (essentially consisting of two posts I made on MathLinks a longer time ago): Erdös-Ginzburg-Ziv: From any $ 2n - 1$ integers, someone can find exactly $ n$ of them, such that their sum is divisible by $ n$. At first, some requisites: A monomial in $ n$ variables is a term of the type $ c\cdot x_{1}^{v_{1}}x_{2}^{v_{2}}...x_{n}^{v_{n}}$ and it's degree is defined as $ v_{1} + v_{2} + ... + v_{n}$. Then for a polynomial $ p(x_{1},x_{2},..,x_{n})$ in $ n$ variables (which is a sum of such monoms by definition), the degree $ \mathrm{deg}(p)$ is defined as the highest degree occuring in it's monomials. Now it's possible to state the important theorem of Chevalley-Warning: Let $ p$ be a prime and $ f_{1}(x_{1},x_{2},..,x_{n}) ,\ f_{2}(x_{1},x_{2},..,x_{n}) ,\ ... ,\ f_{k}(x_{1},x_{2},..,x_{n})$ be $ k$ polynomials in $ n$ variables $ x = (x_{1},x_{2},...,x_{n})$. If we have $ \mathrm{deg}(f_{1}) + \mathrm{deg}(f_{2}) + ... + \mathrm{deg}(f_{k}) < n$, then the number of $ \mod p$ different solutions to the system \[ \\ f_{1}(x_{1},x_{2},..,x_{n})\equiv 0\mod p \\ f_{2}(x_{1},x_{2},..,x_{n})\equiv 0\mod p \\ ... \\ f_{k}(x_{1},x_{2},..,x_{n})\equiv 0\mod p \] is divisible by $ p$. Proof: Lets work in the field $ \mathbb{F}_{p}$ (because this prevents a lot of writing and means nothing else than everything is $ \mod p$). We need a Lemma: Let $ k\in\mathbb{Z}, 0\leq k < p - 1$, then $ \sum_{x\in\mathbb{F}_{p}}x^{k} = 0$ (here $ x^{k}$ is seen as polynomial, thus $ x^{0}$ means the constant polynomial $ 1$) Proof of Lemma: $ z^{k} - 1 = 0$ has at most $ k$ solutions $ z$ in our field. As $ k < p - 1$, there is a nonzero $ y\in\mathbb{F}_{p}$ such that $ y^{k} - 1\neq 0$. Now we get \[ \sum_{x\in\mathbb{F}_{p}}x^{k} = \sum_{xy^{ - 1}\in\mathbb{F}_{p}}(xy)^{k} = y^{k}\sum_{x\in\mathbb{F}_{p}}x^{k} \] giving $ (y^{k} - 1)\cdot\sum_{x\in\mathbb{F}_{p}}x^{k} = 0$, resulting in$ \sum_{x\in\mathbb{F}_{p}}x^{k} = 0$ as $ y^{k} - 1\neq 0$. Back to the proof of the theorem: Let be $ s$ the number of solutions of the system of equations. We want to prove $ s = 0$ in $ \mathbb{F}_{p}$ (be aware of that this just means that the number of solutions is divisible by $ p$). Lets consider the polynomial $ R(x) : = \prod_{i = 1}^{m}\left(1 - \left(f_{i}\left(x_{1},...,x_{n}\right)\right)^{p - 1}\right)$. Then $ s = \sum_{x\in\mathbb{F}_{p}^{n}}R(x)$, because $ R(x) = 1$ iff $ x$ is a solution and $ = 0$ otherwise. Now lets look at the monoms $ g(x) = c\cdot\prod_{i = 1}^{n}x_{i}^{v_{i}}$ that occure in $ R$. For any single one of them, there is an $ i$, w.l.o.g. $ i = 1$, with $ v_{i} < p - 1$, because otherwise the condition on the degrees would not be fulfilled. But then \[ \sum_{x\in\mathbb{F}_{p}^{n}}g(x) = \sum_{x_{1}\in\mathbb{F}_{p}}\sum_{x_{2}\in\mathbb{F}_{p}}...\sum_{x_{n}\in\mathbb{F}_{p}}g(x) = c\cdot\sum_{x_{1}\in\mathbb{F}_{p}}x_{1}^{v_{1}}\cdot\sum_{x_{2}\in\mathbb{F}_{p}}...\sum_{x_{n}\in\mathbb{F}_{p}}x_{2}^{v_{1}}x_{3}^{v_{1}}... x_{n}^{v_{1}} \] and the last one is $ 0$ as $ \sum_{x_{1}\in\mathbb{F}_{p}}x_{1}^{v_{1}} = 0$ by the lemma. So $ s = 0$ because we are summing up monoms summing up to $ 0$. This proves the theorem. Now let's start a proof of the large goal, the theorem of Erdös-Ginzburg-Ziv: Let $ EGZ_{n}$ mean the theorem for this special $ n$, so stating that we can choose from any set of $ 2n - 1$ (or more) integers $ n$ of them such that $ n$ divides their sum. Lets split it up: Lemma 1: If we can prove $ EGZ_{a}$ and $ EGZ_{b}$, we can show that $ EGZ_{ab}$ is true, too. Proof: Let $ 2ab - 1$ numbers be given. Since we assume $ EGZ_{a}$ to be true, we can choose $ a$ numbers of them such that their sum $ s_{1}$ is divisible by $ a$. Then $ 2a(b - 1) - 1$ numbers are left, and we can again choose $ a$ of them such that their sum $ s_{2}$ is divisible by $ a$. Go on and on and on till there are just $ a - 1$ numbers left. We calculate to see that we took $ 2b - 1$ times $ a$ numbers this way and call their sums $ s_{1},s_{2},...,s_{2b - 1}$. Now it's nice to have exactly $ 2b - 1$ such sums, so that we can apply $ EGZ_{b}$ and find $ b$ of these $ s_{i}$ such that their sum $ S$ is divisible by $ b$. But looking back at how we got the $ s_{i}$, we see that $ S$ is the sum of exactly $ ab$ of the original numbers. And looking further, their sum is divisible by $ ab$, which we wanted to show. So applying this lemma often enough, we are left with proving the whole theorem for primes only. Thus it suffices to prove the following: Lemma 2: $ EGZ_{p}$ is true for primes $ p$. Proof: Let any $ 2p - 1$ integers $ a_{1},a_{2},...,a_{2p - 1}$ be given. Look at the system \[ x_{1}^{p - 1} + x_{2}^{p - 1} + ... + x_{2p - 1}^{p - 1}\equiv 0\mod p \\ a_{1}x_{1}^{p - 1} + a_{2}x_{2}^{p - 1} + ... + a_{2p - 1}x_{2p - 1}^{p - 1}\equiv 0\mod p \] of equations $ \mod p$ in $ 2p - 1$ variables. Since the sum of their degrees is $ (p - 1) + (p - 1) = 2p - 2$, lower than $ 2p - 1$, the number of variables, we can use the theorem of Chevalley-Warning. There is one solution $ x_{1} = x_{2} = ... = x_{2p - 1} = 0$, and since the number of solutions is divisible by $ p > 1$, there is another solution. For that other solution, set $ y_{i} = x_{i}^{p - 1}$. By Fermat's theorem, $ y_{i}\equiv 0\mod p\iff x_{i}\equiv 0\mod p$ and $ y_{i}\equiv 1\mod p$ otherwise. We conclude that all $ y_{i}$ are $ \equiv 0,1\mod p$. By definition, we have that not all $ y_{i}$ are $ 0$, but the first of the two equations says \[ y_{1} + y_{2} + .. + y_{2p - 1}\equiv 0\mod p \] giving that exactly $ p$ of the $ y_{i}$ are $ \equiv 1\mod p$ (and the others $ 0$). Setting this into the second one \[ a_{1}y_{1} + a_{2}y_{2} + .. + a_{2p - 1}y_{2p - 1}\equiv 0\mod p \] shows us that a sum of exactly $ p$ of the $ a_{i}$ is $ \equiv 0\mod p$, in other words divisible by $ p$, finishing the proof q.e.tee.

I just wanted to note that there is needed a very little correction to ZetaX's proof. ZetaX wrote: Now it's nice to have exactly $ 2b - 1$ such sums, so that we can apply $ EGZ_{b}$ and find $ b$ of these $ s_{i}$ such that their sum $ S$ is divisible by $ b$. But looking back at how we got the $ s_{i}$, we see that $ S$ is the sum of exactly $ ab$ of the original numbers. And looking further, their sum is divisible by $ ab$, which we wanted to show. From the fact that, for example, $ b|s_1+s_2...+s_b$ it doesn't follow that $ ab|s_1+...+s_b$. But of course that's not a problem, since we can write $ s_i=ak_i$ and from the numbers $ k_1, k_2, ..., k_{2b-1}$ we can choose $ b$ of them with the sum divisible by $ b$. And then everything is allright.

As ZetaX mentioned Erdös-Ginzburg-Zif's theorem follows from Chevalley-Warning or Cauchy-Davenport theorem.And the last theorem has very elementary and short proof by induction,that I've found out at TST,as the first theorem was given just like one of our problems.And this proof doesn't use any polynomials just some beautiful combinatorics ideas... I didn't post it because maybe this proof was already discussed here...But if not,I can post the solution.

Erken wrote: I didn't post it because maybe this proof was already discussed here...But if not,I can post the solution. Well, I don't see it in this topic, so go ahead.

Let me at first prove particular case of Cauchy-Davenport Theorem(let me call it T.E's lemma : Let $ A_1,A_2,\dots,A_n$ be two-element subsets of $ \mathbb{Z}_p$,where $ p$ is prime number.Then the following inequality holds: $ |A_1 + A_2 + \dots + A_n|\geq\min\{p,n + 1\}$. Proof: We will proceed by induction on $ n$: It is not hard to check that theorem holds for $ n = 2$. Suppose that we've already proved the theorem for $ n\leq k - 1$. First case:$ k\leq p - 1$: Let $ A_i = \{x_i,y_i\}$,for all $ i = 1,2,\dots,k$. Suppose to the contrary that $ |A_1 + A_2 + \dots + A_k| < k + 1$,it follows that $ |A_1 + \dots + A_{k - 1}| = |A_1 + A_2 + \dots + A_k| = k$. And let $ S = A_1 + \dots + A_{k - 1} = \{S_1,S_2,\dots,S_k\}$ and $ S' = A_1 + A_2 + \dots + A_k$. Also let's consider two sets $ X = \{S_1 + x_k,S_2 + x_{k},\dots,S_k + x_k \}$ and $ Y = \{S_1 + y_k,S_2 + y_k,\dots,S_k + y_k\}$. It is clear that $ |X| = |Y| = k$ and $ \boxed{X = Y\subset S'}$,otherwise we would obtain a contradiction. Therefore,sum of elements in $ X$ and $ Y$ are equal,so: $ S_1 + S_2 + \dots + S_k + k\cdot x_k = S_1 + S_2 + \dots + S_k + k\cdot y_k$,which is equivalent to $ p$ divides $ k(x_k - y_k)$ but $ k < p$ and $ x_k\neq y_k$.Contradiction. Second case: $ k\geq p$ is obvious. Now let's prove our theorem: Erdös-Ginzburg-Zif: From any $ 2n - 1$ integers,someone can find exactly $ n$ of them,such that their sum is divisible by $ n$. Proof: As it was mentioned by ZetaX it is enough to consider the case when $ n$ is prime. Let $ a_{2p - 1}\geq a_{2p - 2}\geq \dots\geq a_1$ be given integers.As we did it before,we will consider two cases and again one of them is obvious : First case: When there exist $ i\in\mathbb{N}$,such that $ a_i = a_{i + p - 1}$,then we can take these $ p$ equal integers. Second case: When $ a_i\neq a_{i + p - 1}$,for all $ i\in\mathbb{N}$. Let $ A_i = \{a_i,a_{i + p - 1}\}$,where $ i = 1,2,\dots,p - 1$ and $ a_{2p - 1}$ doesn't belong to any set $ A_i$. Applying T.E's lemma: $ \boxed{|A_1 + A_2 + \dots + A_{p - 1}|\geq p}$,therefore, $ A_1 + A_2 + \dots + A_{p - 1} = \mathbb{Z}_p$. But it means that: $ \boxed{- a_{2p - 1}\in A_1 + A_2 + \dots + A_{p - 1}}$. So their sum is divisible by $ p$. Q.E.D Note:I hope you will enjoy my proof,any comments would be appreciated.