The start point is $(0,0,0)$. The "step vector" is $(2,3,6)$. I can variate this, so it can be $(3,6,2)$ and so on, and it can be negative too, like $(6,2-,3)$. I can't step over $(99,99,19)$ and I can't step under $(0,0,0)$. What is the minimum step to reach the finish $(99,99,19)$ point, if I can? And with other step vector, $(2,3,5)$ and $(2,3,4)$? I tried write a solver program in python but it doesn't work yet.
Asked
Active
Viewed 33 times
0
-
Where is this problem from? – M. Winter Apr 18 '18 at 17:25
1 Answers
1
If we use the Manhattan metric in the first two coordinates and think of having your steps of $2$ in the third you need to get $198$ from the origin with steps of length $9$. It takes $22$ steps for that. Using $2$ in the third coordinate all the time will not work because $19$ is odd. We imagine using one $3$ in the third coordinate, which makes the total distance we can get in the first two coordinates $197$. We can add one with one more step by swapping two more $3$s into the third axis and negating a $3$. We can then write $$99=10\cdot 6 + 13 \cdot 3\\99=13\cdot 6+6\cdot 3+1\cdot(-3)+3\cdot 2\\ 19=2\cdot 3 + 1\cdot (-3)+14\cdot 2 +6 \cdot (-2)$$ Note that the coefficients on each line sum to $23$. You need an arrangement of steps that satisfies your constraint that the third coordinate does not exceed $19$
Ross Millikan
- 374,822
-
-
The same approach will work. You want most of the long steps in the first two coordinates because you have so much farther to go there. Find the minimum number of steps based on distance, then see if you run into a problem and add a step or two if necessary. – Ross Millikan Apr 18 '18 at 21:15
-
I see. For the (2,3,4) vector I found a 31-step-solution this way. But with the (2,3,5) vector I didn't solve. Is it possible? – valaki plda Apr 19 '18 at 06:07
-
No, it isn't possible. Every step is of even length and your destination is an odd distance away. You can't add even numbers to get an odd. – Ross Millikan Apr 19 '18 at 14:14