24 Jun '08 04:54

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

- Joined
- 09 Aug '06
- Moves
- 5363

- Joined
- 25 Oct '02
- Moves
- 20443

Out of my mind- Joined
- 09 Aug '06
- Moves
- 5363

- Joined
- 12 Sep '07
- Moves
- 2668

24 Jun '08 12:211 editI 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.- Joined
- 31 May '07
- Moves
- 696

24 Jun '08 14:43modulo 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.- Joined
- 25 Aug '06
- Moves
- 0

- Joined
- 25 Oct '02
- Moves
- 20443

Out of my mind- Joined
- 12 Sep '07
- Moves
- 2668

25 Jun '08 08:572 editsAh 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?- Joined
- 12 Sep '07
- Moves
- 2668