Resurrection and revitalisation

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.)

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.

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.

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}

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.

Right, I've proved that 2n-1 never works now, so I can give a hint: do it for prime n first.

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?

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.

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?

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?

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.

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...