The problem was:
(x,y) with x<y is transformed to (2x,y−x). This process is repeated. For what initial x,y can we end up with equal numbers. x,y are positive integers.
Solution
Notice that starting with (x,y) is essentially starting with (ax,ay) for any integer a≥1.
So assume that x and y have no common factor.
Now for the numbers to become eventually equal, x+y must be even, as the sum of the two numbers never changes.
Thus after one step (2x,y−x), both these numbers are even, and so we can divide out by 2
Every time we divide out by 2 the sum is halved.
Thus if x+y=2MQ, where Q is odd greater than 1, eventually we end up with an odd sum, and so cannot equalize.
Thus the condition is that if x/y=p/q in lowest terms, then equalization occurs iff p+q=2m.
(x,y) with x<y is transformed to (2x,y−x). This process is repeated. For what initial x,y can we end up with equal numbers. x,y are positive integers.
Solution
Notice that starting with (x,y) is essentially starting with (ax,ay) for any integer a≥1.
So assume that x and y have no common factor.
Now for the numbers to become eventually equal, x+y must be even, as the sum of the two numbers never changes.
Thus after one step (2x,y−x), both these numbers are even, and so we can divide out by 2
Every time we divide out by 2 the sum is halved.
Thus if x+y=2MQ, where Q is odd greater than 1, eventually we end up with an odd sum, and so cannot equalize.
Thus the condition is that if x/y=p/q in lowest terms, then equalization occurs iff p+q=2m.
This comment has been removed by the author.
ReplyDeleteCan't we solve this in a different way?
ReplyDeleteSuppose x, y are nonnegative reals. WLOG suppose x + y = 2.
Let's say that current state can be encoded by a real value `a` -1 <= a <= 1, such that first bucket has a + 1 water, and second bucket has 1 - a water.
Then at each step a is transformed like
f(a) = 2a - sgn(a)
And we stop only when at some point f(a) is integer.
Now consider g(a) = 2a
Now, notice that (f^n)(a) is integer iff (g^n)(a) is integer.
So we stop if and only if a is of form n/(2^k). n integer, k >= 0
Hi!
DeleteSorry I didn't see your comment earlier. I believe your approach might be right, but needs a little bit more elaboration to make it clearer.
I presume you convert (x,y) to (2xx+y,2yx+y) and apply your reasoning?
I believe it might be right and seems to give the equivalent condition as was got in the blogpost with the initial a being y−xy+x (assume y>x).