0

I have a set of rational numbers, and the only allowed operation is calculating the mean of a subset and adding it to the set. The goal is to generate zero.

I tried brute-forcing this problem with S = {7, -4} but failed.

Does this problem have a name and is there an efficient algorithm to solve it or show if there is a solution?

Toby Kelsey
  • 3

1 Answers1

1

(7,-4), (7,-4,-4), (7,-1,-4,-4),(7,-1,-1,-4,-4),(7,-1,-1,-1,-4,-4),(7,0,-1,-1,-1,-4,-4)

You can duplicate numbers since you can take the mean of a 1 number subset and add it to the set. Then you are basically looking for a sum to zero

Algorithmically, sort original array, look for the closest two numbers to zero, if they are multiples of each other you are golden, if they are not then they are coprime and you can solve $ax+by=1 or -1$ then duplicate however 1's necessary to have a sum to zero.

Obviously your set must contain both positive and negative numbers for this to work

chris c
  • 369
  • I hadn't considered duplicates, but they could be allowed in my specific problem. If we have a set in the mathematical sense with no duplicates, is the problem much harder? – Toby Kelsey Jan 13 '15 at 15:31
  • If you don't allow duplicates then if the starting numbers are coprime then you are restricted to ax+by = 1 meaning a linear combination will not get you zero. So you cant do it – chris c Jan 13 '15 at 15:33
  • I don't see how coprimality prevents summing a subset to zero when you have proper fractions in the set. Could you flesh that out a bit? – Toby Kelsey Jan 13 '15 at 15:49
  • I see what you mean, I guess I was working from the perspective of the integers, but if you have rational numbers things get a little complicated, for example would you consider a convergent sequence to zero valid by your rules? – chris c Jan 13 '15 at 15:53
  • Obviously we can keep averaging numbers of opposite sign to get smaller. In my context I need to get exactly zero in a finite number of steps. I can use duplicates (I think) to get this in practice but was wondering if I could do it without them. – Toby Kelsey Jan 13 '15 at 16:04