Please turn on javascript in your browser to play chess.
Posers and Puzzles

Posers and Puzzles

  1. 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.
  2. Standard member TheMaster37
    Kupikupopo!
    24 Jun '08 09:21
    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
  3. 24 Jun '08 11:52
    Originally posted by TheMaster37
    Working on it, modulo n seems to simplify the problem alot
    You are on the right track.
  4. 24 Jun '08 12:21 / 1 edit
    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.
  5. 24 Jun '08 14:43
    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.
  6. 24 Jun '08 19:52
    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.
  7. Standard member TheMaster37
    Kupikupopo!
    25 Jun '08 06:15 / 1 edit
    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.
  8. 25 Jun '08 08:57 / 2 edits
    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?
  9. 26 Jun '08 10:40
    David or smaia, could one of you clear up my half-proof above. Please don't give me any hints on the other half!