very nice - Erdos theorem and generalizations

[vdto]

Anyone know solutions for the following beautiful theorem by Erdos

Given 2n-1 arbitrary integers, we always can find n numbers whose sum is divided by n

I have read 2 different solutions for this and I'll post them later.

Now here are the generalizations:

Given 4n-3 arbitrary integer pairs (a,b), we always can find n pairs whose sum is divided by n


Let n be odd number. Given 2n-1 arbitrary DISTINCT elements of Z_n x Z_n, we always can find n elements whose sum is (0,0)

I don't want to give references to the above problems because it may discourage some of our problem-attackers out there.

Happy solving!!!

vdto

[Nemo]

[sam-n]

i also have two soln for the first one u can use challway warning theorom and the other one u can use this lemma assume that A and B is a subset of{0,1,2,3,...,p-1} ,here p is prime number,assume that :
A+B={a+b (mod p) such that }then we have :
if u want i can complete my lemma

[sam-n]

have a look!

[vdto]

To: Nemo, read the question again

"Given 2n-1 arbitrary integers, we always can find n numbers whose SUM is divided by n "

To: Sam-n,

The two proofs that you mentioned are different from ones that I have read. The first proof that I knew uses Pigeon Hole Principle, the second uses an equality and Fermat theorem. We can post them all later.

the second problem:
"Given 4n-3 arbitrary integer pairs (a,b), we always can find n pairs whose sum is divided by n "
is still an open problem, I didn't say it in my first post because I don't want to discourage some youngster out there.

the third problem
"Let n be odd number. Given 2n-1 arbitrary DISTINCT elements of Z_n x Z_n, we always can find n elements whose sum is (0,0) "
has been proved recently for the case n prime > 73, the proof also uses Cauchy-Davenport inequality but it is very long with many cases.
for the general case (n odd) the problem is still open.

vdto

[Charlydif]

Actually the second problem it isnt an open one. Kemnitz conjecture was recently proved (last year) by Crhistian Rehier (or something like that) a german student who went to last year imo.
The solution to this one uses chevally too, but maybe something of linear algebra. The problem for general dimension is still open and waiting for a new idea. I anyone is intrested write my Charlydif@hotmail.com.
Anyway here is a skecth for the 2n-1 problem (the first one), firste by some standard argument we reduce the problem to prime numbers. Now if n is prime, take any p-sum race it to the p-1-power and sum over all posibble p-sums.
If there isnt any p-sum with zero sum then each sumand will equal 1 mod p. Now try to explote this to get a contradiction.
I know several proof of this problem, maybe later i posted some of them. On the other hand i dont no any proof which doesnt reduce it to the prime case, anyone have one?

[pbornsztein]

Have you a copy of the proof for the two-dimensional case?

Pierre.

[vdto]

To: Charlydif

[Nemo]

To vdto : sorry , I'm wrong !

I think it's not difficult prove that : Given 3 arbitrary integers, we always can find 2 numbers whose sum is divisible by 2, Given 5 arbitrary integers, we always can find 3 numbers whose sum is divisible by 3, and futher, by inductive we will prove that this problem.
I have an idea : Given 2n-1 arbitrary integers, we always can find n-1 pair numbers same parity, when if n is even we only can prove that in n-1 arbitrary integers, we always can find n-1 numbers whose sum is divisible by n/2 ,... we can continue grow this idea

I will try and post it later .

[Charlydif]

Well i will try to explain the general idea of the proof (strictly speaking of the way i see it).
Call v(n)= the number of substes of n vectors with zero sum. We wan to prove that v(p)>0.
By Chevally we can get
1) 1-v(p)+v(2p)-v(3p)+v(4p).... =0 mod p if the number of vectors is at least 3p-2.
Working a lit it be more we can get
2) v(p)-2v(2p)+3v(3p)-...=0 mod p if there are at least 4p-2 vectors.
3) if there is a counter example add one vector, and by counting the number of pair(A,B) where m is the a p-subset with zero sum, and B is a 3p-subset with zero sum and B contains A we can get v(p)=v(3p).
Collecting 1,2,3 we get a contradiction.

1) is an easy consequence of chevally, 3)is a counting argument that uses 1), 2) is harder and in fact we can prove more in fact
Sum= (i^kV(ip)*(-1)^i) = 0 mod p if there are at least p(3+k)-2 vectors....
pbornsztein or anybody intrested on the proof, please send my an email to charlydif@hotmail.com (vdto, i am sending you an email right now)

[Charlydif]

Well here is another proof for n=a prime number, in fact is Sam-n proof but with out mention cauchy-davenport inequalite (which was given in the recent bulgarian olympiad as a problem).
Lemma= Any set of 2k-1 numbers mod p, have at least k different k-sums mod p, or there is an element repeted at least k times. (this can be proved by an easy induction).
Proof: take n=p

Another proof use the general theorem of Olson (i stated only a particualr case)= Given 2p-1 vectors of Z^2, there is a subset with zero sum mod p. (for a proof search for vess posts on "Hard isl problem or something like that, he proved in two diferents ways.
Proof: If a1,a2,...a(2p-1), are the number take the following set of vectors (a1,1),(a2,1),(a3,1)............ apply the theorem and we are done.
I know another proof that uses linear algebra and some Permanents.... but all of them reduce it to the prime case.

[Charlydif]

Is Christian Rehier here? Anyone from germany know him?