From: cd@newsun-graphe.lri.fr (Charles Delorme)
Subject: Re: Subset sum divisible by n
Date: 16 Jan 2000 09:53:21 GMT
Newsgroups: sci.math
Summary: Erdos-Ginzburg-Ziv theorem

In article <85ql7b$jb2$1@uwm.edu>, David G Radcliffe <radcliff@alpha2.csd.uwm.edu> writes:
|> Does every set of 2n-1 integers contain a subset 
|> with n elements whose sum is divisible by n?
|> 
|> 

Yes, this is known as Erdos-Ginzburg-Ziv theorem,
Here is a reference

Eros, Ginzburg, Ziv
a Theorem in additive number theory
Bull. Res. Council Israel 10 (1961)

Sincerely yours
-- 
Charles Delorme  tous les mégalomanes
LRI              ont une signature
cd@lri.fr        à étages
==============================================================================

From: Robin Chapman <rjc@maths.ex.ac.uk>
Subject: Re: Subset sum divisible by n
Date: Sun, 16 Jan 2000 15:08:11 GMT
Newsgroups: sci.math

In article <85ql7b$jb2$1@uwm.edu>,
  David G Radcliffe <radcliff@alpha2.csd.uwm.edu> wrote:
> Does every set of 2n-1 integers contain a subset
> with n elements whose sum is divisible by n?

Yes. It's quite easy to see that if this is valid for n = r
and n = s then it's also true for n = rs. I'll omit this. So we can
reduce to the case where n = p is prime, which is not so trivial.

Let a_1, ..., a_{2p-1} be the numbers and let I = {1,..., 2p-1}
be the index set. For a subset J of I let S(J) be the sum of the
a_j for j in J.

We count the sum T of the S(J)^{p-1} (mod p) over all J with |J| = p
in two ways.

First of all each term in S(J)^{p-1} is a monomial in the a_i s.
Each such monomial contains k different a_i where 1 <= k < p.
This monomial occurs in (2p-1-k choose p - k) = (2p-1-k)!/[(p-k)!(p-1)!]
of the S(J) and this number is divisible by p. Hence T = 0 (mod p).

Now if all of the S(J) are non-zero then S(J)^{p-1} = 1 (mod p).
Thus T = (2p-1 choose p) =/= 0 (mod p), a contradiction.

--
Robin Chapman, http://www.maths.ex.ac.uk/~rjc/rjc.html
 "`The twenty-first century didn't begin until a minute
  past midnight January first 2001.'"
   John Brunner, _Stand on Zanzibar_ (1968)


Sent via Deja.com http://www.deja.com/
Before you buy.