## Is my (size 200) subset sum proof good? [closed]

I'm trying to prove that given 200 integers (not necessarily all distinct), you can pick 100 of them have a sum divisible by 100. I'm wondering if this is a good proof and if you would give me some advice on how to write it better. Thanks!

(A) For any 3 element set, there exists a 2 element subset which sums to an even number. This is clear if we consider cases, the 3 element set must be of the form {even,even,-} or {odd,odd,-} and these two elements sum even.

(B) For any 9 element set, there exists a 5 element subset which sums to a multiple of 5. This is verified by exaustive computation, We only have to consider the sets of numbers mod 5, so that is 5^9 cases to test.

(C) So if we are now give a 200 (= 2*2*2*5*5) element set will we always be able to find a 100 element subset, which sums to a multiple of 100? By (A) we can reduce the problem to a stronger one, take out two elements which sum even and sum then and halve the result - we iterate this until it can't be done any more. This gives us a new set of 99 arbitrary integers (we discard the remaining two integers from the original 200 element set). If we can now find a size 50 (= 100/2) subset which sums to a multiple of 50 we have proved (C). We do this factoring out 2 operation again to get a 49 element set and again to get a 24 element set, let us consider the same operation factoring out 5 instead of 2. Now 24 = 5+5+5+5+4 and 5+4 is 9, so we are given a set of 4 integers which must sum to a multiple of 5, this is not likely -- we really do need 9 arbitrary integers, well there are 4 left over from the factoring out 5 and there was that one left over from factoring out 2 the first time.. So we do have 9 arbitrary integers and thus a subset of size 5 summing to something divisible by 5 and hence (C) is proved.

-
Note: this is the case $n = 100$ of the Erdos-Ginzburg-Ziv Theorem, except that theorem says that you need only 199 numbers, not 200. – Pete L. Clark Mar 3 2010 at 16:59
I do not think that Mathoverflow is meant as a place where you can get your proofs checked. – Carsten Schultz Mar 3 2010 at 17:18
okay sorry I'm new and thanks about EGZ too where can I read a proof of that? – muad Mar 3 2010 at 17:20
On page 11 of math.uga.edu/~pete/4400ChevalleyWarning.pdf – Ben Linowitz Mar 3 2010 at 17:25
Closed. I think for now mathoverflow is not an appropriate place for checking proofs. Please come over to meta and start a thread if you think this should change. – Scott Morrison Mar 3 2010 at 19:14
show 2 more comments