From: jons5451@telcel.net.ve
Newsgroups: sci.math
Subject: Re: Ex-Putnam winner and ex-Math professor stumped by seemingly elementary arithmetic problem
Date: Tue, 31 Mar 1998 13:26:47 -0600

In article <01bd5cb7$2bdbaf30$1f6104ce@pc30>,
  "Larry Penn" <penn@ellington.com> wrote:
>
> Larry Penn and George Zettler would like to know whether anyone knows a
> proof of the following:
>
> For any positive integer N>0, and for any set of integers a(1), a(2), ... ,
> a(2*N-1) of 2N-1 integers, there exists some subset a(k(1)), a(k(2)), ...,
> a(k(N)) of size N such that SUM(a(k(i)), i=1 to N) is divisible by N.
>
> In other words, out of any set of 2N-1 integers, there is a subset of size
> exactly N whose sum is divisible by N.

This is the case m=k of the Erdos-Ginzburg-Ziv theorem:

  Let m >= k >= 2 be integers such that k divides m. Then given m+k-1
  integers a_1,...,a_{m+k-1}, there is a subset I of {1,2,...,m+k-1}
  such that |I| = m and \sum_{i \in I}a_i = 0 (mod k).

reference:
Erdos, Ginzburg, Ziv; Theorem in additive number theory,
 Bull. Research Council Israel, 10F (1961), 41-43.

Greetings,
Jose H. Nieto

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/   Now offering spam-free web-based newsreading
==============================================================================

From: kubo@jacobi.math.brown.edu (Tal Kubo)
Newsgroups: sci.math
Subject: Re: Ex-Putnam winner and ex-Math professor stumped by seemingly elementary arithmetic problem
Date: 2 Apr 1998 20:43:06 GMT

In article <6frfrn$5g0$1@nnrp1.dejanews.com>,  <jons5451@telcel.net.ve> wrote:
>> [...] out of any set of 2N-1 integers, there is a subset of size
>> exactly N whose sum is divisible by N.
>
>This is the case m=k of the Erdos-Ginzburg-Ziv theorem:
>
>  Let m >= k >= 2 be integers such that k divides m. Then given m+k-1
>  integers a_1,...,a_{m+k-1}, there is a subset I of {1,2,...,m+k-1}
>  such that |I| = m and \sum_{i \in I}a_i = 0 (mod k).

You mean m=2, mk-1 given integers, and |I|=(m-1)k -- but there is
no extra generality other than applying the original version 
several times to extract (m-1) disjoint k-subsets with sum=0 mod k.
The hard part is to prove the  2P-1 --> P statement above. You can
do it when P is prime (which suffices) by looking at the sum of the
(P-1)^th powers of sums of the k-element subsets, and counting the
result in two different ways.