16 Oct 05
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.)
19 Oct 05
Originally posted by royalchickenI need some clarification on this problem.
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
Originally posted by BigDoggProblemI'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:
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]
{6, 12, 18, 24, 30, 31, 37, 43, 49, 55}
20 Oct 05
Originally posted by royalchickenAhh, I see where I misread now.
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
Originally posted by royalchickenI 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:
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
Originally posted by BigDoggProblemWouldn't that be a spoiler?
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?