Dado un par de enteros, doblar uno e incrementar el otro hasta igualdad

Question

Tengo un problema de matemáticas, y no tengo idea de cómo resolverlo. Yo la vi por primera vez en el Código de Golf StackExchange, aquí. El cartel de no hay alusión a sabiendas de que no es una prueba, pero no se presentaron pruebas.

Vamos a empezar con un par de enteros $a$$b$. Hacemos doble y añadir una a la otra. Tenemos el poder de decidir que el doble y que el incremento de la. Repetimos esta "duplicación/+1" del proceso, hasta que los dos enteros son iguales.

Por ejemplo, comenzando con $(2, 5)$ podemos duplicar el 5 y el incremento de la 2 para dar $(3, 10)$. Entonces, podemos duplicar el tres y el incremento del 10 por $(6, 11)$. Podemos duplicar el seis y el incremento del 11 $(12, 12)$ - y ahora que hemos hecho los números son iguales.

Dado cualquier par de enteros, es siempre posible hacerlas igual el uso de estos pasos?

Parcial De La Prueba Todos los pares de números negativos terminará. Esto se basa en el hecho de que la duplicación de 0 es 0. Si empezamos con un par de números negativos, podemos repetidamente añadir uno a uno de los números hasta que llega a 0. Mientras que el otro número se ha doblado varias veces, podemos repetidamente decremento hasta que es demasiado, llega a 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

Este problema ha sido resuelto en reddit por nuestro propio Lopsy:

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

Voy a resumir esta respuesta. Llame a la operación $(x,y)\mapsto (x+1,2y) $ operación $1$, y llame a la otra $(x,y)\mapsto(2x,y+1) $ operación $2$.

Puedes empezar con un par de $(a,a+b)$ donde $a,b>0$ (posiblemente después de cambiar los números). Deje $\ell$ ser un número para ser elegido más tarde: realizar las acciones siguientes:

• operación #1 en el total de $b$ veces: $$(a+b,2^b(a+b))$$
• operación #2 un total $b-\ell+1$ veces: $$(2^{b-\ell+1}(a+b),2^b(a+b)+b-\ell+1)$$
• operación #1 una vez: $$(2^{b-\ell+1}(a+b)+1,2^{b+1}(a+b)+2b-2\ell+2)$$
• operación #2 un total $\ell$ veces: $$(2^{b+1}(a+b)+2^\ell,2^{b+1}(a+b)+2b-\ell+2)$$

Inicialmente, la diferencia absoluta entre los números se $b$, y ahora es $$ |2^\ell-2b+\ell-2|\etiqueta{$*$} $$ Mientras podemos optar $\ell$, de modo que $(*)$ es de menos de $b$, de los que tenemos un procedimiento para disminuir la diferencia absoluta de los dos números, que puede ser repetido hasta que son iguales.

Resulta que para todos los $b\ge 2$, existe un $\ell$ que satisface $(*)$. Reorganizar, esto equivalente a la solución de $$ b\le 2^{\ell}+\ell-2\le 3b\etiqueta{$**$} $$ El resto de la prueba es, entonces, (i) demuestre que $(**)$ tiene una solución para todas las $b\ge 2$, lo que puede implicar la fuerza bruta de la comprobación de algunos casos pequeños, y (ii) mostrar cómo manejar el caso especial $(a,a+1)$ (existe un 10 paso de la solución).