I was practicing some questions on diophantine equation when I saw a classical jump problem where we had to determine if we can reach to point 'n' from point 0 by taking jumps of length 'a' or 'b' in either direction(i.e. left or right) on an infinite number line. However I was thinking for variation of this question where we have an additional constraint that at any point of time in our path, we should never go outside the range [0, m] where 'm'is any number greater than or equal to 'n'. Out of all the testcases that I was able to make, I observed that such constraint holds if n is divisible by gcd(a, b) (same as the normal variaton), but I am not able to prove it mathematically for this variation. Can anyone help me in this?
Formally: Can anyone give me a mathematical proof that if n is divisible by gcd(a, b) then there exists a way in which we can reach 'n' in such a way that we are always within the range [0, m] (m >= n), or if my assertion is wrong then I want to know about the flaw in this statement.
i do not understand clearly what you want to ask. But in case,you are asking if a*x- b*y =n is solvable for natural numbers x and y(<=n)such that gcd(a,b)|n , then this is true .And proof follows from Euclidean algorithm.
I am asking that, suppose n = 21, a = 15, b = 9 and m = 29 then the equation is 15x + 9y = 21, so we can see that for x = 2 and y = -1, this equation is satisfied, but we also have to make sure that at any point of time we never stepped out of the valid range which is [0, m]. Here, in this example we can make this sure by taking first jump of length 15 forwards then one jump of length 9 backwards and finally on more jump of length 15 forwards, but I want to know that can we get a "valid" path like this always? Of course, there doesn't exist a path if n is not divisible by gcd(a, b).
By "valid" path I mean a path in which we never step out of the range [0, m] while jumping.
Then i think the answer depends on the value of "m" you choose. For e.g. if you take m=21 for 40x + 15y = 10 , then the answer is "NO". But if you extend the value of m to 40 or more , then answer is "YES".
Well, the main problem arises when m is greater than all other variables. Is it correct to say that the answer will always be "yes" if m is greater than all the other variables and n mod gcd(a, b) = 0 holds?
It's not correct either. Take (m, n, a, b) = (24, 24, 15, 21). If you first move +15 then you are stuck. If you move +21, then you have to move -15 and you are stuck again.
No, i dont think it is correct to say that answer will be YES if m > max(a,b). e.g. you can have 100x + 15y = 30 hold for m=30(but 100 > 30).
In your example m is 30 which is less than a
How? clearly a=100 > 30.
We can't always do this. The simplest example is (m, n, a, b) = (1, 1, 2, 3)