Operaciones repetidas en $(a,b)$

Question

Para cada par de enteros $(a,b)$, definir la secuencia de $S_{(a,b)}$ como:

Si $a_{n-1} < b_{n-1}$$(a_{n},b_{n}) = (2a_{n-1},b_{n-1}+1)$; de lo contrario, si $b_{n-1} < a_{n-1}$$(a_{n},b_{n}) = (a_{n-1}+1,2b_{n-1})$. Si $a_n = b_n$, entonces hemos terminado.

En otras palabras, en cada paso que damos el doble de la menor y agregar uno a la mayor de $(a,b)$. Nos detenemos al $a_n = b_n$, es decir, llegar a un par de $(c,c)$.

Mi pregunta es: para cualquier $a, b$ estamos garantizados para terminar en un par de $(c,c)$?

Answer 1

Dudo que la terminación en $(c,c)$ se produce por cada par. Acabo de empezar con $(4,3)$ y se obtuvo la siguiente matriz que muestra la trayectoria de la primera pareja de iteraciones como resultado. Aquí cada fila es uno de recorrer el par inicial y la diferencia entre los elementos de la pareja: $$\pequeño \begin{array} {rr|r} a & b & a-b \\ \hline 4 & 3 & 1 \\ 5 & 6 & -1 \\ 10 & 7 & 3 \\ 11 & 14 & -3 \\ 22 & 15 & 7 \\ 23 & 30 & -7 \\ 46 & 31 & 15 \\ 47 & 62 & -15 \\ 94 & 63 & 31 \\ 95 & 126 & -31 \\ 190 & 127 & 63 \\ 191 & 254 & -63 \\ \vdots & \vdots & \vdots \end{array}$$ Las diferencias (en la tercera columna) siga un evidente patrón y sin analizar en detalle estoy seguro de que este primer par de números tiene una infinita trayectoria.

[actualización]
Si miramos los números a lo largo de la trayectoria de iteraciones, entonces parece que el siguiente es importante.
Suponga $a_0 \lt b_0$ . A continuación, vamos a escribir todas las iteraciones mientras que $a_j \lt b_j$ como uno de los pasos y queremos

$$ a_1=a_0 \cdot 2^{k} > b_1=b_0 + k >b_0 + k-1 > a_0 \cdot 2^{k-1} >a_0 $$

Vamos a ver, que $b_1$ se encuentra en el intervalo de $a_1 .. a_1/2$. La siguiente iteración, para construir $b_2 = 2^j \cdot b_1 > a_1 + j$ necesidades, a continuación, sólo una $j$ menor que $k$ y a lo largo de más iteraciones que el requerido exponente en $2$ converge a $1$. Así, en el largo plazo, la transformación se reduce a $a_{k+1} = 2 \cdot a_k , b_{k+1}=b_k+1 $ y viceversa $a_{k+2} = a_{k+1}+1 , b_{k+2}=2 \cdot b_{k+1} $ .

Creo que, esto es la observación crucial (y debería ser más riguroso: no hay la menor $k$ a partir de donde la regla anterior es válido si no se ha $a=b$)

Luego de continuar en este camino, la escritura de dos pasos en uno de este es $$a_{k+2} = 2^1 \cdot a_k +1 \qquad \qquad b_{k+2}=2^1 \cdot b_k+2 \\ a_{k+4} = 2^2 \cdot a_k +3 \qquad \qquad b_{k+4}=2^2 \cdot b_k+6 \\ a_{k+6} = 2^3 \cdot a_k +7 \qquad \qquad b_{k+6}=2^3 \cdot b_k+14 \\ $$ La generalización de este da $$a_{k+2r}+1 = 2^r \cdot (a_k+1) \\ b_{k+2r}+2=2^r \cdot (b_k+2)$$

y esto demuestra, que las diferencias $d_k=(b_k+2) - (a_k+1)$ ampliar a $d_{k+2r} = 2^r \cdot d_k$ (si no $a_k - b_k=1$).
Y si las diferencias de cambio, las trayectorias de $(a_k,b_k)$ no puede ser constante.
Si $a_k - b_k = 1$ algunos $k$, entonces todas las otras diferencias se $1$.

Answer 2

Si usted comienza con un par de la forma $(a, 2^ra - r)$, entonces usted consigue $(2a, 2^ra- (r-1))$, es decir, un par de la forma $(a', 2^{r-1}a' -(r-1))$. Repetir la operación, se obtiene un par de la forma $(c, c)$.

Puedo afirmar que este es el único camino. De lo contrario, tendríamos que conseguir un par de la forma $(a, 2^ra - r)$ a partir de algo distinto de $(a/2, 2^ra - (r+1))$. La única posibilidad de que este es $(a-1, \frac{2^ra - r}{2})$. Pero para $r\geq 2$, $a>0$ tenemos $\frac{2^ra - r}{2} > a$; cuando $r=1$ $2^ra - r$ no es divisible por 2; y al $r=0$ sólo $(a-1, a/2)$, por lo que no es realmente diferente a la par que sabemos que funciona.