Given a pair of integers, double one and increment the other until equality

Question

I have a math problem, and I have no idea how to solve it. I first saw it over on the Code Golf StackExchange, here. The poster there hinted at knowing that there is a proof, but no proof was provided.

We start with a pair of integers $a$ and $b$. We double one and add one to the other. We have the power to decide which to double and which to increment. We repeat this "doubling/+1" process, until the two integers are equal.

For example, starting with $(2, 5)$ we can double the 5 and increment the 2 to give $(3, 10)$. Then, we can double the three and increment the 10 for $(6, 11)$. We can double the six and increment the 11 for $(12, 12)$ - and now we have made the numbers equal.

Given any pair of integers, it it always possible to make them equal using these steps?

Partial Proof All pairs of negative numbers will terminate. This relies on the fact that doubling 0 is 0. If we start with a pair of negative numbers, we can repeatedly add one to one of the numbers until it hits 0. While the other number will have been doubled several times, we can repeatedly decrement it until it too, hits 0.

$(-6, -3) \to (-12, -2) \to (-24, -1) \to (-48, 0) \to (-47, 0) \to (-46, 0) \to \cdots \to (0, 0)$

Answer 1

This problem has been solved on reddit by our very own Lopsy:

https://www.reddit.com/r/mathriddles/comments/2v6eaj/doubling_and_adding_1/

I will summarize this answer. Call the operation $(x,y)\mapsto (x+1,2y) $ operation $1$, and call the other one $(x,y)\mapsto(2x,y+1) $ operation $2$.

You start with a pair $(a,a+b)$, where $a,b>0$ (possibly after switching the numbers). Let $\ell$ be a number to be chosen later: perform the following actions:

• operation #1 at total of $b$ times: $$(a+b,2^b(a+b))$$
• operation #2 a total $b-\ell+1$ times: $$(2^{b-\ell+1}(a+b),2^b(a+b)+b-\ell+1)$$
• operation #1 once: $$(2^{b-\ell+1}(a+b)+1,2^{b+1}(a+b)+2b-2\ell+2)$$
• operation #2 a total $\ell$ times: $$(2^{b+1}(a+b)+2^\ell,2^{b+1}(a+b)+2b-\ell+2)$$

Initially, the absolute difference between the numbers was $b$, and now it is $$ |2^\ell-2b+\ell-2|\tag{$*$} $$ As long as we can choose $\ell$ so that $(*)$ is less than $b$, than we have a procedure to decrease the absolute difference of the two numbers, which can be repeated until they are equal.

It turns out that for all $b\ge 2$, there exists an $\ell$ which satisfies $(*)$. Rearranging, this equivalent to solving $$ b\le 2^{\ell}+\ell-2\le 3b\tag{$**$} $$ The remainder of the proof is then to (i) show that $(**)$ has a solution for all $b\ge 2$, which may involve brute force checking for some small cases, and to (ii) show how to handle the special case $(a,a+1)$ (there exists a 10 step solution).