0

(Apologies since this was likely asked before, but I cannot find it. )

Is there a way to find the shortest path from some value V to some destination value D using only addition of values from a given set of numbers S?

For example, starting value V = 0. Destination value D=5. Allowed operation is only addition (+) and only values from the following set: S={4,-3}

The solution is 0+4+4-3=D (or any other ordering of these numbers), but nevertheless, requires at least 3 operations.

Another example, starting value V = 0. Destination value D=4. Allowed operation is only addition (+) and only values from the following set: S={3,-7} D=0+3+3+3+3+3+3-7-7=4. It requires at least 8 operations.

Finally, starting value V = 0. Destination value D=2. Allowed operation is only addition (+) and only values from the following set: S={3,-6, -9} Is impossible to complete.

So the question is: How to find the shortest path to get from starting value V to destination value D, by only adding numbers from set S?

How is this called? How can this be figured out? Many thanks!

Michael Seltenreich
  • 222
  • 1
  • 2
  • 14
  • What have you tried? E.g. Can you solve for integers solutions to $ 4 = 3a - 7b$? – Calvin Lin May 29 '20 at 01:04
  • It is impossible because the three numbers $3, -6, -9$ are multiples of $3$ which on addition or subtraction will always give a multiple of $3$. – SarGe May 29 '20 at 01:21
  • @Doubtnut How to find the shortest path to get from starting value V to destination value D, by only adding numbers from set S? (in the case of 3,-6,-9) the shortest path doesn't exist (or equals infinity) – Michael Seltenreich May 29 '20 at 11:06
  • @CalvinLin, I didn't understand your question – Michael Seltenreich May 29 '20 at 11:07
  • @Doubtnut I'm not sure what you mean. For instance, how do you find the shortest path from 0 to 391 using -2,5,11? How can you verify it's the shortest path? How can you tell in the general case if you can get to D in a finite number of steps? (3511 + 25 + 2*-2) – Michael Seltenreich May 29 '20 at 11:12
  • Ok! So you want a general formula? – SarGe May 29 '20 at 11:16
  • 1
    So I guess what you're looking for, is given integers $n$ and $x_0, x_1, \ldots x_n$, you want $$ a_0 x_1 + a_0 x_1 + \ldots + a_n x_n = n $$ so that $\sum_j |a_j| $ is minimised? The question goes: if we find a set of factors $a_i$, is there another set that also satisfies the same relation? – Matti P. May 29 '20 at 11:16
  • Yes, this is exactly what I'm trying to figure out! Thank you for putting it in math speak :) – Michael Seltenreich May 29 '20 at 11:21
  • 1
    @MattiP. It is restricted to non-negative $a_j$. Note that only addition is allowed. Subtraction seems to appear because the set S contains negative values. – Calvin Lin May 29 '20 at 14:56

0 Answers0