- 16 Oct '05 00:23For 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.) - 19 Oct '05 17:13

I need some clarification on this problem.*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.)

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. - 19 Oct '05 18:14

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:*Originally posted by BigDoggProblem***I need some clarification on this problem.**divisible by n?'

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

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]

{6, 12, 18, 24, 30, 31, 37, 43, 49, 55} - 20 Oct '05 04:09

Ahh, I see where I misread now.*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}

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. - 21 Oct '05 19:24

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

{ 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? - 21 Oct '05 23:52

Wouldn't that be a spoiler?*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?