Consideramos los pares [math](a,b) donde [math]a y [math]b son enteros positivos. Las operaciones permitidas son
[math](a,b) \rightarrow (a,2b); [math](a,b) \rightarrow (2a,b); [math](a,b) \rightarrow (a-b,b) si [math]a>b; [math](a,b) \rightarrow (a,b-a) si [math]a<b.
Determinar si a partir de [math](1,1), mediante alguna secuencia de operaciones permitidas, se puede obtener
a) el par [math](2005,2010);
b) el par [math](2004,2006).
We gave you a start so you'd know what to do
You've seen how it works, now it's over to you (...)
For there's so much more to explore! Numberblocks - https://www.youtube.com/watch?v=KzTR72_srTU
a) No es posible. Sea [math]d>1 un número impar, y supongamos que en algún momento obtenemos un par en el que ambos números son divisibles por [math]d. Afirmo que el par anterior a ese también cumple esta propiedad. En efecto, si nuestro par es de la forma [math](a,2b), tenemos que [math]d divide a [math]a y a [math]2b, como es impar, esto último implica que [math]d también divide a [math]b; si el par es de la forma [math](2a,b) el razonamiento es análogo; si el par es de la forma [math](a-b,b) tenemos que [math]d divide a [math]b y también divide a [math]b+(a-b) = a; y si el par es de la forma [math](a,b-a) el razonamiento es análogo. Por inducción resulta que en todos los pares anteriores ambos números son divisibles por [math]d, sin embargo esto es absurdo porque el par inicial era el [math](1,1), que no lo cumple. Luego no se puede obtener un par en el que ambos números sean divisibles por [math]d. Fijando [math]d=5 obtenemos la conclusión deseada.
b) Sí, es posible. Notemos que nos basta con mostrar una manera de obtener el par [math](501,1003), pues en tal caso duplicamos dos veces el primer número y una vez el segundo y obtenemos el par [math](2004,2006). Más aún, como [math]1003 \equiv 1 \pmod{501}, nos alcanza con obtener un par de la forma [math](501,k) con [math]k \geq 1003 y [math]k \equiv 1 \pmod{501}, pues en tal caso le podemos restar [math]501 al número tantas veces como sea necesario para llegar al [math]1003, logrando así el objetivo.
Comenzando con el par [math](1,1), duplicamos [math]9 veces el primer número, obteniendo el par [math](512,1), luego hacemos [math]11 veces la operación de restarle al número más grande el número más chico, obteniendo el par [math](501,1), y finalmente duplicamos el segundo número [math]\phi(501) veces. Por el teorema de Fermat-Euler, [math]2^{\phi(501)} \equiv 1 \pmod{501}, así que el objetivo está cumplido.
We gave you a start so you'd know what to do
You've seen how it works, now it's over to you (...)
For there's so much more to explore! Numberblocks - https://www.youtube.com/watch?v=KzTR72_srTU
Si [math]N = 2^k t con [math]t impar, digo que [math]t es la parte impar de [math]N.
Observación: La parte impar del máximo común divisor de [math]a y [math]b es invariante por las operaciones.
Demostración de la observación: Multiplicar uno de los números por [math]2 a lo sumo duplica el [math]\text{mcd}. Entonces no altera su parte impar.
Restarle un número al otro mantiene igual el [math]\text{mcd} y por lo tanto también su parte impar (esto es por el algoritmo de Euclides)[math]\blacksquare
Afirmación: Sea [math]d es un número impar. Entonces se puede llegar del par [math](d,d) al par [math](a,b)[math]\Leftrightarrow la parte impar de [math]\text{mcd}(a,b) es [math]d.
Notemos que la afirmación prueba que no se puede llegar del par [math](1,1) al par [math](2005,2010) y que se puede llegar del par [math](1,1) al par [math](2004,2006).
Demostración de la afirmación:
Notemos que [math]\Rightarrow es consecuencia inmediata de la afirmación.
Para probar [math]\Leftarrow vamos a pensar las operaciones de atrás para adelante. Cambio las operaciones por:
Si [math]a es par, pasar del par [math](a,b) al par [math](\frac{a}{2},b)
Si [math]b es par, pasar del par [math](a,b) al par [math](a,\frac{b}{2})
Pasar del par [math](a,b) al par [math](a+b,b)
Pasar del par [math](a,b) al par [math](a,a+b)
Notemos que la observación sigue valiendo cuando uno hace las operaciones de atrás para adelante.
Doy un algoritmo que permite llegar de un par [math](a,b) a un par [math](d,d) con [math]d impar. Una vez que probemos esto por la observación sigue lo que queremos.
Algoritmo:
Primero divido por [math]2 ambos números hasta que sean impares.
Si son iguales logré lo que necesitaba y el algoritmo termina. Si no, supongamos que tengo el par [math](a,b). Notemos que [math]a y [math]b son impares.
Si [math]a<b paso al par [math](a,a+b) y luego a [math](a,\frac{a+b}{2}). Si el segundo número sigue siendo par lo divido por hasta que sea impar
Si [math]a>b paso al par [math](a+b,b) y luego a [math](\frac{a+b}{2},b). Si el primer número sigue siendo par lo divido por hasta que sea impar
Vuelvo al principio del parrafo y repito el procedimiento.
Cada vez que uno hace este procedimiento el máximo de los dos números del par disminuye. Como este número es mayor que [math]0, el algoritmo termina y estamos[math]\blacksquare
Guía de $\LaTeX$ (sirve para escribir ecuaciones como $2^{3\times 2}+1=13\cdot 5$)
A) No es posible. Fijarse que el MCD entre a y b, o queda constante o se multiplica por 2. Entonces, no se puede partir de (a,b) con MCD=1 y llegar a (a,b) con MCD=5.
B) Es posible. Los pasos (de manera resumida):
(1, 1)
(2048, 1)
(2005, 1)
(2005, 1003)
(1002, 1003)
(2004, 1003)
(2004, 2006)
Nota: para pasar de (2005, 1) a (2005, 1003) fijarse que hay un $k>1$ tal que $2^k = 2005*{c}_{1} + 1$. Fijarse que $2^{k - 1} = 2005*{c}_{2} + 1003$. Por lo tanto, pasamos de (2005, 1) a (2005, $2005*{c}_{2} + 1003$) y de ahí a (2005, 1003).
