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

Solution 1:

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

Edit: just to clarify, this proof of is not mine, I took it from the book "Teoria dos Números: Um Passeio com Primos e Outros Números Familiares Pelo Mundo Inteiro", which is a book about number theory in portuguese.