7
$\begingroup$

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?

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

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

See this, section 4. (page 11)

|cite|improve this answer
$\endgroup$

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.