Proving that among any $2n - 1$ integers, there's always a subset of $n$ which sum to a multiple of $n$

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

Solution 2:

Posts can also show how to prove you can multiply results with $2$ known cases which work to get a larger case which also works, e.g., if the result works for $n = i$ and $n = j$, then it also works for $n = ij$. From this, you can extend known results for a few specific cases only to show it works for an infinite set of values.

This answer proves it for the specific case of when $n = 3$. Also, A question relevant to EGZ theorem? shows how to prove it in the general case.

Solution 3:

There are sometimes posts involving asking for proving the result for some subset of possible values of $n$. This would normally involve using some specific property of the subset to prove the result. The only posts I could find which involves this are for powers of $2$:

• 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}$.
• West German Mathematics Olympiad 1981
• Prove for any number n, it is possible to select $X = 2^n$ numbers from $2^{n+1}$ numbers s.t. the sum of X is divisible by $2^n$

Solution 4:

Most of the questions on this site involve asking to prove the result for a specific, relatively small, value of $n$ (although sometimes the question specifies a larger value than $2n-1$ for the number of integers to choose from). The answers for $n$ being prime usually involve some sort of sets of cases and using the pigeon-hole principle, while the non-prime values involve handling each of the prime factor(s) separately and then showing how they can be combined to get the final result.

• For $n = 2$, there are no posts I could find, possibly because it's very simple to do. Since there are only $2$ parities, i.e., even & odd, then among any $3$ integers, at least $2$ must have the same parity, so the sum of those $2$ integers will be even.
• For $n = 3$, there are:
  • How do I prove that among any $5$ integers, you are able to find $3$ such that their sum is divisible by $3$?
  • Prove that for any set of 5 integers, there is at least one subset of 3 integers whose sum is divisible by 3
• For $n = 4$, there is:
  • Given 7 arbitrary integers,sum of 4 of them is divisible by 4
• For $n = 5$, there are:
  • Given any nine numbers, prove there exists a subset of five numbers such that its sum is divisible by $5$.
  • Pigeon hole principle with sum of 5 integers
• For $n = 6$, there is:
  • Among any $11$ integers, sum of $6$ of them is divisible by $6$
• For $n = 9$, there is:
  • Pigeon - Hole principle and remainder modulus