# Sum of $n$ numbers divisible by $n$

Given a collection of (not necessarily distinct) integers, how large must the collection be to guarantee that for a particular $n$, there is a subcollection of $n$ numbers summing to a multiple of $n$?

A glance shows that for any $n$, at least $2n-1$ are required, since if we have a collection of $n-1$ 0's and $n-1$ 1's, then there is no way to sum to a multiple of $n$. Is there an elegant way to prove $2n-1$ is always sufficient?

• If we have a subcollection of $0$s... then isn't $0$ a multiple of $n$? – Omnomnomnom Jul 23 '17 at 20:38
• Just to clarify: you require that we use $n$ numbers, yes? Not $≤n$. Thus , having $n-1$ $0's$ doesn't solve the problem. – lulu Jul 23 '17 at 20:40
• If I have understood you correctly, this is the content of the Erdős–Ginzburg–Ziv theorem. – lulu Jul 23 '17 at 20:42
• Here is the original Erdos paper bolyai.hu/~p_erdos/1961-25.pdf – Raffaele Jul 24 '17 at 9:31
• Yes, I did mean exactly $n$ numbers, no less. Thanks everyone for linking me to resources! – Bolton Bailey Jul 24 '17 at 19:24

There is an elegant proof of this using the Chevalley Warning theorem which easily proves it for prime $n$ (then a multiplicative property is proved for the rest).