[Math] Proving that among any $2n – 1$ integers, there’s always a subset of $n$ which sum to a multiple of $n$

Question

How can one prove that among any $2n – 1$ integers, there's always a subset of $n$ which sum to a multiple of $n$?

It is not hard to see this is equivalent to show that among $2n-1$ residue classes modulo $n$ there are $n$ whose sum is the zero-class. Thus, this problem is an example of a Zero sum problem.

Also, the general case was first proven in the $1961$ paper of Erdős, Ginzburg and Ziv.

This is a resource intended to be part of the ongoing effort to deal with abstract duplicates. There are quite a few posts here related to proving that among any $2n – 1$ integers, there's always a subset of $n$ which sum to a multiple of $n$, with varying degrees of generality from using only specific values of $n$ to proving it for all cases. Each of my following answers deal with a degree of generality by explaining it and then linking to the related existing posts.

However, there are many ways to deal with this problem, including some which may not yet be handled by any posts on this site. Some examples, as suggested by quid's question comment, include:

• What are some different ways to prove the results? Basically all solutions use the pigeon-hole principle in some way, so can this be solved without using that principle? Also, as MathOverflow's EGZ theorem (Erdős-Ginzburg-Ziv) asks, can the general solution, as in the EGZ theorem, be proven without using the Chevalley–Warning theorem (or a variant of its proof)?
• The answer links to Use Pigeonhole to show of any set of $2^{n+1}-1$ positive integers is possible choose $2^{n}$ elements such that their sum is divisible by $2^{n}$. where one answer shows how you can prove it using induction. Are there any other special cases of subsets of $n$ which can be solved on their own apart from the linked ones related to powers of $2$?
• The answer gives a proof for $n = 2$, and gives examples of specific $n$ which have been asked on this site of $3$, $4$, $5$, $6$ and $9$. However, are there any other small values of $n$ which can also reasonably be handled explicitly?

Answer 1

There are several posts which deal with proving the general result. These are:

• Given any 2n-1 integers, prove that there are always n of them which add up to a multiple of n
• Given $n$ integers, is it always possible to choose $m$ from them so that their sum is a multiple of $m$?
• Show that in any set of $2n$ integers, there is a subset of $n$ integers whose sum is divisible by $n$.

There's also a post about this on MathOverflow:

• EGZ theorem (Erdős-Ginzburg-Ziv)