2
$\begingroup$

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:

$\endgroup$
7
  • $\begingroup$ "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. " Is it possible to extend this answer to prove it for all n ? Secondly, have you come across a simple intuitive proof that is easy to understand ? All the answers I have seen so far, use some theorems which is too complicated for me to understand . $\endgroup$ Apr 2, 2021 at 22:02
  • $\begingroup$ @HemantAgarwal There are several linked posts for proving the general result in this answer. As for "an easy to understand answer", unfortunately there'll always be a certain amount of inherent complexity in any general proof. I'm not sure what would constitute for you a simple enough proof. Nonetheless, as stated in my third paragraph, the first proof was in the $1961$ paper of Erdős, Ginzburg and Ziv. Although far from trivial, I was able to understand it. $\endgroup$ Apr 2, 2021 at 22:09
  • 1
    $\begingroup$ Winkler, Mathematical Puzzles, copyright 2004, page 122, poses a problem he calls Even Split: "Prove that from every set of $2n$ integers, you can choose a subset of size $n$ whose sum is divisible by $n$." Let's note that this implies the $2n-1$ result: given $2n-1$ integers, toss in one more integer to make the sum of the $2n$ integers a multiple of $n$; use the Winkler formulation to assert the existence of a subset of size $n$ whose sum is divisible by $n$; note that the complement of this subset is also a set of size $n$ whose sum is divisible by $n$; (continued next comment) $\endgroup$ Feb 27, 2023 at 4:58
  • 1
    $\begingroup$ (continued from previous comment) then one of these two subsets does not contain the extra integer we tossed in at the beginning, so it's a subset of size $n$ of the original set of $2n-1$ integers, with sum divisible by $n$. I like to think of the extra integer as a catalyst which made the reaction go without being used up in the end result, sort of like the $18$th cow in that old problem. Anyway, Winkler's solution appears on pages $132-133$. It doesn't use any advanced math, but I'm not game to write it out here. $\endgroup$ Feb 27, 2023 at 5:05
  • 1
    $\begingroup$ Sorry, $18$th camel: math.stackexchange.com/questions/3773496/… and mathoverflow.net/questions/271608/17-camels-trick $\endgroup$ Feb 27, 2023 at 5:16

5 Answers 5

1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$:

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ can you prove for all n ? maybe through induction or any other method ..I have seen a lot of answers on this site but they use some theorems etc .I am looking for an easy to understand answer . $\endgroup$ Apr 2, 2021 at 21:59
  • $\begingroup$ @HemantAgarwal See my comment response to your very similar comment to my question. $\endgroup$ Apr 2, 2021 at 22:10
0
$\begingroup$

Posts may potentially alter the general conditions, such as restrict the set of available congruences and use a set of available integers which is considerably larger than necessary, with the idea being that a specific method can be used to solve the problem. The only such post I know of is the following one which deals with choosing $19$ integers from a set of $181$ integers which only include the $10$ square congruences modulo $19$, with this being solved directly using the pigeon-hole principle on those available congruences:

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .