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

Posers and Puzzles

  1. Standard member royalchicken
    CHAOS GHOST!!!
    16 Oct '05 00:23
    For what positive integers m and n is it possible to construct an m-element set of positive integers such that the sum of any n of them is not divisible by n?

    (Hint: Someone asked me this for n=6. I told them that m=10 is the largest for which this can be done. The generalisation follows the exact same argument I made.)
  2. 16 Oct '05 09:48
    n=1 m=0,

    For n>=2 you could put down n-1 0s (or any multiples of n) and n-1 1s (or any numbers congruent to 1 mod n). So m=2n-2 is always possible. I am not sure that this is the best stratergy though. i.e. can't show that 2n - 1 can't be done for any n.
  3. Subscriber BigDoggProblem
    The Advanced Mind
    19 Oct '05 17:13
    Originally posted by royalchicken
    For what positive integers m and n is it possible to construct an m-element set of positive integers such that the sum of any n of them is not divisible by n?

    (Hint: Someone asked me this for n=6. I told them that m=10 is the largest for which this can be done. The generalisation follows the exact same argument I made.)
    I need some clarification on this problem.

    Do you mean that the 'sum of any n of them is not evenly divisible by n?'

    If n=6 and m=10 (per your example), my set is
    { 6, 12, 18, 24, 36, 42, 48, 54, 60, 66 }.
    The elements are all multiples of 6, so any summing of them must lead to a result that is evenly divisible by 6. Changing m won't help.
  4. Standard member royalchicken
    CHAOS GHOST!!!
    19 Oct '05 18:14
    Originally posted by BigDoggProblem
    I need some clarification on this problem.

    Do you mean that the 'sum of any n of them is not [b]evenly
    divisible by n?'

    If n=6 and m=10 (per your example), my set is
    { 6, 12, 18, 24, 36, 42, 48, 54, 60, 66 }.
    The elements are all multiples of 6, so any summing of them must lead to a result that is evenly divisible by 6. Changing m won't help.[/b]
    I'm looking for a set for which NO n-element subset isums to a multiple of n. Since I wasn't asking about the n=6, m=10 case, an example is:

    {6, 12, 18, 24, 30, 31, 37, 43, 49, 55}
  5. Subscriber BigDoggProblem
    The Advanced Mind
    20 Oct '05 04:09
    Originally posted by royalchicken
    I'm looking for a set for which NO n-element subset isums to a multiple of n. Since I wasn't asking about the n=6, m=10 case, an example is:

    {6, 12, 18, 24, 30, 31, 37, 43, 49, 55}
    Ahh, I see where I misread now.

    Basically, if we let x=6, the set you gave is

    x, 2x, 3x, 4x, 5x, 5x+1, 6x+1, 7x+1, 8x+1, 9x+1

    Dividing each term by six (or x) and listing only the remainder gives

    0,0,0,0,0,1,1,1,1,1

    which is why the set works - if the modulii (is that a word?!?) could sum to a multiple of six, it would fail. The set could also be { 6, 7, 12, 13 etc. and it would work.

    From the example given, it would seem that m = (n - 1) * 2, but I have not found a way to prove it yet. One also has to consider possibilities with remainders greater than 1. I haven't found a pattern to it yet.
  6. Standard member royalchicken
    CHAOS GHOST!!!
    21 Oct '05 16:17
    Right, I've proved that 2n-1 never works now, so I can give a hint: do it for prime n first.
  7. Subscriber BigDoggProblem
    The Advanced Mind
    21 Oct '05 19:24
    Originally posted by royalchicken
    Right, I've proved that 2n-1 never works now, so I can give a hint: do it for prime n first.
    I see why 2n-1 does not work when the remainders are only 0 and 1. But I'm having trouble proving that combinations involving other remainders must always fail. For example, attempts like:

    { 6,13,20,27,34,41,43,50,57,64 } giving remainders 0,1,2,3,4,5,1,2,3,4

    won't work because I can add 3 pairs of remainders to get sixes.

    More subtle attempts such as

    { 11,17,23,29,35,39,45,51,56,62 } giving remainders 5,5,5,5,5,3,3,3,2,2

    are a bit more difficult to eliminate. Here I can do it by adding
    5+5+5+5+2+2 = 24.

    But how do I prove there is no clever combination of remainders greater than 1 that will not sum to a multiple of six?
  8. 21 Oct '05 22:12
    Originally posted by BigDoggProblem
    if the modulii (is that a word?!?) could sum to a multiple of six, it would fail. The set could also be { 6, 7, 12, 13 etc. and it would work.

    The word is modulus,I think.
  9. Standard member royalchicken
    CHAOS GHOST!!!
    21 Oct '05 23:52
    Originally posted by BigDoggProblem
    I see why 2n-1 does not work when the remainders are only 0 and 1. But I'm having trouble proving that combinations involving other remainders must always fail. For example, attempts like:

    { 6,13,20,27,34,41,43,50,57,64 } giving remainders 0,1,2,3,4,5,1,2,3,4

    won't work because I can add 3 pairs of remainders to get sixes.

    More subtle atte ...[text shortened]... re is no clever combination of remainders greater than 1 that will not sum to a multiple of six?
    Wouldn't that be a spoiler?
  10. Subscriber BigDoggProblem
    The Advanced Mind
    22 Oct '05 00:22
    Originally posted by fetofs
    The word is modulus,I think.
    Right, but I have more than one of them, so I need the plural...is it moduluses or modulii?
  11. Subscriber BigDoggProblem
    The Advanced Mind
    22 Oct '05 00:24
    Originally posted by royalchicken
    Wouldn't that be a spoiler?
    Wasn't sure if I needed to know it before trying prime-number n's or not.
  12. 22 Oct '05 00:37
    Originally posted by BigDoggProblem
    Right, but I have more than one of them, so I need the plural...is it moduluses or modulii?
    Or maybe just two modulus...