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

Solution 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).