most recent 30 from http://mathoverflow.net 2013-05-26T01:19:54Z http://mathoverflow.net/feeds/question/16981 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/16981/is-my-size-200-subset-sum-proof-good muad 2010-03-03T16:50:58Z 2010-03-03T16:50:58Z

<p>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!</p> <p>(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.</p> <p>(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.</p> <p>(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.</p>