15
$\begingroup$

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)$

$\endgroup$
  • $\begingroup$ Do you mean $a_n = 2^na$ and $b_n = b+n$? But of course if $a>b>1$ then $a_n>b_n$ for all $n\in\{0,1,2,3,...\}$. $\endgroup$ – Michael May 4 '18 at 18:31
  • 4
    $\begingroup$ he means $(i,j)$ can be taken to $(2i,j+1)$ or $(i+1,2j)$ $\endgroup$ – Jorge Fernández Hidalgo May 4 '18 at 18:32
  • $\begingroup$ @JorgeFernández yes, that's what I mean. $\endgroup$ – moonchunkcheese May 4 '18 at 18:33
  • $\begingroup$ what are we supposed to do? Show it is always possible to make them equal? $\endgroup$ – Jorge Fernández Hidalgo May 4 '18 at 18:33
  • 1
    $\begingroup$ Sorry I deleted my answer. I think the right way to approach this problem is in binary, but although I thought the proof was simple, it's not quite as simple as I thought, so the hint I wrote is insufficient. I'll come back and expand when I get a chance. $\endgroup$ – Brian Tung May 4 '18 at 18:49
11
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I don't think you need that $a$ is positive, and to solve the special case $(a, a+1)$ you can just note that $(a+1, 2a+2)$ will have a difference greater than 2 as long as $a \ge 1$, and $(2a, a+2)$ will have a difference greater than 2 if $a < 1$. $\endgroup$ – Contravariant May 5 '18 at 0:29
  • $\begingroup$ Did you mix up the names of the operations? $\endgroup$ – kmm May 5 '18 at 15:46
  • $\begingroup$ @kmm Indeed, fixed! $\endgroup$ – Mike Earnest May 5 '18 at 17:51
  • 2
    $\begingroup$ @Contravariant You still need a solution for $b=1$ because the descent could pass into $b=1$, and there is no natural number solution to $b + 2 < 2^{\mathcal l} + \mathcal{l} < 3b+2$ for $b=1$, so an alternative is needed. $\endgroup$ – DanielV May 5 '18 at 18:23
  • $\begingroup$ @Contravariant I agree; my strategy allows you to decrease the absolute difference from $b$ to some $c$ for which $0\le c<b$, but otherwise gives no control over $c$. You could start from $b$ then decrease to $1$, but then the move $(a,a+1)\mapsto (a+1,2a+2)$ could bounce you back to $b$, so you get in a cycle instead of converging to $0$. $\endgroup$ – Mike Earnest May 7 '18 at 14:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.