Prove this theorem

From every set of 2n integers, you can choose a subset of size n whose sum is divisible by n.

Originally posted by smaia
From every set of 2n integers, you can choose a subset of size n whose sum is divisible by n.

Working on it, modulo n seems to simplify the problem alot 🙂

Originally posted by TheMaster37
Working on it, modulo n seems to simplify the problem alot 🙂

You are on the right track.

I have been trying an approach that doesn't seem to work. I remember solving a problem:

Prove that in a set of n integers there is a subset such that the sum of its elements is divisible by n.

Oooh! I remember seeing something like this from an Olympiad problem. I can't quite remember, but it was a little stronger than the problem smaia gave us. In the Olympiad it was also to prove a subset of n integers divisible by n, but that time there was only 2n-1 numbers to choose from, 1 less than what smaia gives us.

modulo n, you can have n-1 lots of a number that is x mod n, and n-1 lots of a number that is y mod n, but then as soon as you have a number that is z mod n, a number can be divisible by n by taking the z mod n number and a configuration of the x mod n and y mod n numbers.

Thus the maximum numbers you can have to avoid divisibility is n-1 + n-1 or 2n-2. If we have 2n, we are above this maximum.

I am happy with this, other people won't be.

Originally posted by smaia
From every set of 2n integers, you can choose a subset of size n whose sum is divisible by n.

Prove first for prime n. Then prove that if the theorem holds for n=k and for n=t, then it holds for n=kt.

Originally posted by doodinthemood
but then as soon as you have a number that is z mod n, a number can be divisible by n by taking the z mod n number and a configuration of the x mod n and y mod n numbers.

Prove this.

Ah yes. I can do the second part of David's way. I can do it for 2n-1 numbers as well.

The proposition is that among a set of 2n-1 integers, there are always n such that the sum of them is divisible by n.

Suppose this is true for n=p and n=q (p,q prime). Let us look at when n=pq.
Then we will have a set of 2pq-1 integers which i will call A, where we are trying to find pq of them whose sum divides pq.

Take 2p-1 integers from A. Because the proposition is proven for n=p, we can find p integers, whose sum is divisible by p. Remove these p numbers from A. Clearly we can do this with the set remaining, etc.

After we have found 2q-2 distinct subsets of A, each of p elements and the sum being divisible by p, we will have 2pq-1-(2pq-2p)=2p-1 numbers remaining in A. And again, as the proposition is proven for n=p, we can again choose a subset.

So we can find 2q-1 distinct subsets of A, each of p elements and each with a sum divisible by p. Let the sums of each of these subsets by S(1), S(2), S(2)... S(2q-1).

Consider the set {S(1), S(2), ... S(2q-1)} Clearly there are 2q-1 elements, and because the proposition is proven for n=q, we can choose q of these sums, and the total is divisible by q.

Now replace each of the sums with the p original elements from A. Look at the sums we have chosen. We have ended up choosing pq elements, and the sum of them is divisible by q and since each of the 'sub-sums' is divisible by p, the total is divisible by p. As p and q are prime, the pq elements have a total divisible by pq.

Therefore, if the proposition is true from primes p,q, it is true also for pq.

Looking over the explanation, I realise it may be long-winded and unclear. Someone fix things up for me please!

As for proving it for all primes, I will start on fiddling with modular arithmetic, and possible FLT, I am so sure FLT has something to do with all this.

EDIT: Err, this only proves it for all square-free numbers
EDIT: Scrap that, p and q don't actually have to be prime, do they?

David or smaia, could one of you clear up my half-proof above. Please don't give me any hints on the other half!