The problem was:
$(x,y)$ with $x \lt 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 \ge 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 = 2^M Q$, 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 = 2^m$.
$(x,y)$ with $x \lt 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 \ge 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 = 2^M Q$, 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 = 2^m$.
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 $(\frac{2x}{x+y},\frac{ 2y}{x+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 $\frac{y-x}{y+x}$ (assume $y \gt x$).