# Show that in any set of $2n$ integers, there is a subset of $n$ integers whose sum is divisible by $n$.

There was a problem in a recent programming competition which my friend solved by assuming the following conjecture:

Show that for any set of $$2n$$ integers, there is a subset of $$n$$ integers whose sum is divisible by $$n$$.

I have thought about this problem for a while but can't seem to prove it, but I couldn't come up with a counter-example either.

A similar problem has a well-known solution: show that for any set of $$n$$ integers, there is a non-empty subset whose sum is divisible by $$n$$.

The proof goes as follows. Suppose the set is $$\{x_1, x_2, \dots, x_n\}$$ and hence define $$s_i = \left(x_1 + x_2 + \dots + x_i\right)\bmod n$$, with $$s_0 = 0$$. Then we have the set $$\{s_0, s_1, \dots, s_n\}$$ with $$n+1$$ elements, but each $$s_i$$ can take only $$n$$ distinct values, so there are two $$i, j$$ with $$i\neq j$$ such that $$s_i = s_j$$. Then $$s_j - s_i = x_{i+1} + x_{i+2} + \dots + x_j$$ is divisible by $$n$$.

However, this approach can't directly be applied to this problem since now we need to ensure that we choose exactly $$n$$ integers.

• you can actually cut it to half of $n$ plus 1 potentially, as any distinct remainders that's when you have two element that are additive inverse. The only question then is how to show it can't be lower.
– user645636
Dec 4 '19 at 13:33

Well, it is true, and in fact you only need $$2n-1$$ integers in order to do so. It was proven by Erdős, Ginzburg and Ziv and it is not a trivial application of pigeon-hole principle.
One way that I know of proving it is using the Chevary-Warning theorem, which states that for $$p$$ prime, given polinomials $$f_1,...,f_n\in\mathbb{Z[x_1,...,x_n]}$$, such that $$\sum_{1\leq i\leq k}deg(f_i)\leq n-1$$ the set $$A=\{(x_1,...,x_n)\in\mathbb{Z}_p^n|f_i(x_1,...,x_n)=0\forall i=1,...,k \}$$ satisfies $$p$$ divides $$|A|$$ (the cardinality of $$A$$).
Using this, we can prove that for $$n$$ prime, given the set $$\{a_1,.,,a_{2n-1}\}$$, the system $$f_1(x_1,...,x_{2n-1})=x_1^{n-1}+...+x_{2n-1}^{n-1}=0\quad(mod p)$$ $$f_2(x_1,...,x_{2n-1})=a_1x_1^{n-1}+...+a_{2n-1}x_{2n-1}^{n-1}=0\quad (mod p)$$ have more than one solution, by the Chevary-Warning theorem (one solution is trivially $$x_i=0$$). As each $$x_i^{n-1}$$ is either 0 or 1, by Fermat's little theorem, a non-trivial solution to the systems corresponds to the choice of $$n$$ numbers such that theirs sum is multiple of $$n$$.
For the cases when $$n$$ is not prime we can use induction over the numbers of prime factos of $$n$$: if there is an anwser for $$m$$ and $$n$$ it is easy to obtain an answer for $$mn$$...