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" 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>, 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.