8
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ See this article and the links out there. $\endgroup$
    – metamorphy
    Oct 10 '19 at 18:21
  • $\begingroup$ 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. $\endgroup$
    – user645636
    Dec 4 '19 at 13:33
2
$\begingroup$

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.

$\endgroup$
1
  • 4
    $\begingroup$ I just want to link the original paper of Erdős, Ginzburg and Ziv. $\endgroup$ Oct 10 '19 at 16:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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