"La CUARenTenA"- Problema 6

[Mórtimer]

Dado un trío de enteros no negativos, en cada paso Mauro elige dos de sus elementos, $a$ y $b$, y cambia uno de ellos por $a+b$ o $|a-b|$.
Probar que existe una constante $r>0$ tal que, para cualesquiera enteros positivos $x,y,z,n$ con $x,y,z < 2^n$, Mauro puede transformar el trío $(x;y;z)$ en $(x';y';z')$ con $x'y'z'=0$ aplicando $rn$ operaciones válidas o menos.

[Mórtimer]

Solución:

Spoiler: mostrar

Vamos a probar que $r=12$ funciona por inducción fuerte en $n$.

Caso base: si $n=1$, el enunciado se satisface trivialmente.
Hipótesis inductiva: supongamos que el enunciado se satisface con $r=12$ para todo $n \in [1;k]$. Vamos a demostrar que también es válido para $n=k+1$.

Supongamos que nuestros números iniciales son SPG $(x,y,z)$ con $0<x<y<z<2^{k+1}$ (si dos de ellos son iguales, con una operación ya terminamos el proceso). Si dos o tres de ellos son mayores o iguales a $2^k$, con a lo sumo $2$ operaciones podemos conseguir que dos de ellos sean menores a $2^k$. Esto es, $(x,y,z) \rightarrow (x,y,z-y) \rightarrow (x,y-x,z-y)$, donde en este caso valdría $z-y<\frac{z}{2}<2^k, y-x<\frac{y}{2}<2^k$. Asumamos entonces que ya tenemos $x<y<2^k$.

Consideremos la siguiente sucesión de números:
$$a_1=x, a_2=y, a_{n+2}=a_{n+1}+a_n, \ \forall \ n \in Z^+$$
Notemos que la sucesión es creciente y por lo tanto, $a_{n+1}=a_n+a_{n-1}<2a_n<a_n+a_{n+1}=a_{n+2}$. Sea $m$ entero no negativo tal que $2^my<z<2^{m+1}y$. Si $m=0$, hacemos $(x,y,z) \rightarrow (x,y,z-y)$ y los tres números son menores a $2^k$, Por lo tanto, por hipótesis, podemos lograr lo pedido en $3+12k<12(k+1)$ operaciones. Si $m \geq 1$, consideremos la subsucesión $a_{i_1}>a_{i_2}> \dots > a_{i_t}$:
$$
a_{i_1} \leq z < a_{i_1+1} \\
a_{i_2} \leq z-a_{i_1} < a_{i_2+1}\\
\dots \\
y \leq a_{i_t} \leq z-a_{i_1}-a_{i_2}-\dots-a_{i_{t-1}}<a_{i_{t}+1} \\
0 \leq z' = z-a_{i_1}-a_{i_2}-\dots-a_{i_t} < y
$$
(Notar que como $a_{n+1}<2a_{n}$, para $x<a_{n+1}<2a_n$ vale que $x-a_n<a_n$).

Como $a_{n+2}>2a_{n}$, tenemos que $a_{2l+2}>2^ly \Rightarrow i_1 \leq 2m+3$ porque de otro modo, $z \geq a_{i_1} \geq a_{2m+4}>2^{m+1}y>z$. Además fijémonos que $t \leq i_1-1 \leq 2m+2$ pues $i_{t} \geq y=a_2$. Realizamos las siguientes operaciones: utilizamos la suma para $(a_{2d-1},a_{2d},*) \rightarrow (a_{2d+1},a_{2d},*) \rightarrow (a_{2d+1},a_{2d+2},*)$ y utilizamos la resta cada vez que aparece en los primeros dos números algún término de la subsucesión. En este caso, si por ejemplo tenemos la situación $(a_{i_t},a_{i_t-1},z)$, lo que hacemos es $\rightarrow (a_{i_t},a_{i_t-1},z-a_{i_t}) \rightarrow (a_{i_t},a_{i_{t}+1},z-a_{t}) \rightarrow \dots$. Finalizamos este primer procedimiento cuando obtenemos $a_{i_1}$ en alguno de los dos primeros términos y $z'=z-a_{i_1}-a_{i_2}+\dots +a_{i_t}$ en el tercero. Luego, procedemos revirtiendo nuestras $i_1-2$ operaciones de los primeros dos términos: $(a_{2d+1},a_{2d+2},*) \rightarrow (a_{2d+1},a_{2d},*) \rightarrow (a_{2d-1},a_{2d},*) \rightarrow \dots$

Con este algoritmo, llevamos a cabo exactamente$2(i_1-2)+t \leq 2(2m+1)+2m+2=6m+4$ y logramos que nuestros tres números sean $x,y,z'<=y<frac{z}{2^m}<2^{k+1-m}$. Por hipótesis inductiva, podemos lograr lo pedido con $12(k+1-m)$ operaciones más. En total, logramos nuestro objetivo con a lo sumo $2+6m+4+12(k+1)-12m \leq 12(k+1)$, lo cual completa nuestra inducción.

Siempre podemos obtener un trío $(x';y';z')$ con $x'y'z'=0$ en $12n$ operaciones válidas o menos $\ \blacksquare$


Nota: es un buen ejercicio para comprender la demostración buscar optimizar la cota $r \leq 12$. Por ejemplo, es posible hallar una cota superior para $t$ más pequeña. No obstante a todo esto, la clave del argumento reside en la subsucesión, la cual nos permite probar que la cantidad de operaciones crece linealmente en función de $n$.