Selectivo 16° Cono Sur 2005 - Problema 6

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Matías V5

Colaborador-Varias OFO - Jurado-OFO 2015 OFO - Jurado-OFO 2016 FOFO 6 años - Jurado-FOFO 6 años OFO - Jurado-OFO 2017
OFO - Jurado-OFO 2018 OFO - Jurado-OFO 2020 OFO - Jurado-OFO 2021
Mensajes: 1088
Registrado: Dom 17 Oct, 2010 4:44 pm
Medallas: 8
Nivel: Exolímpico

Selectivo 16° Cono Sur 2005 - Problema 6

Mensaje sin leer por Matías V5 »

Consideramos los pares [math] donde [math] y [math] son enteros positivos. Las operaciones permitidas son

[math];
[math];
[math] si [math];
[math] si [math].

Determinar si a partir de [math], mediante alguna secuencia de operaciones permitidas, se puede obtener
a) el par [math];
b) el par [math].
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
Avatar de Usuario
Matías V5

Colaborador-Varias OFO - Jurado-OFO 2015 OFO - Jurado-OFO 2016 FOFO 6 años - Jurado-FOFO 6 años OFO - Jurado-OFO 2017
OFO - Jurado-OFO 2018 OFO - Jurado-OFO 2020 OFO - Jurado-OFO 2021
Mensajes: 1088
Registrado: Dom 17 Oct, 2010 4:44 pm
Medallas: 8
Nivel: Exolímpico

Re: Selectivo 16° Cono Sur 2005 - Problema 6

Mensaje sin leer por Matías V5 »

Spoiler: mostrar
a) No es posible. Sea [math] un número impar, y supongamos que en algún momento obtenemos un par en el que ambos números son divisibles por [math]. Afirmo que el par anterior a ese también cumple esta propiedad. En efecto, si nuestro par es de la forma [math], tenemos que [math] divide a [math] y a [math], como es impar, esto último implica que [math] también divide a [math]; si el par es de la forma [math] el razonamiento es análogo; si el par es de la forma [math] tenemos que [math] divide a [math] y también divide a [math]; y si el par es de la forma [math] el razonamiento es análogo. Por inducción resulta que en todos los pares anteriores ambos números son divisibles por [math], sin embargo esto es absurdo porque el par inicial era el [math], que no lo cumple. Luego no se puede obtener un par en el que ambos números sean divisibles por [math]. Fijando [math] obtenemos la conclusión deseada.

b) Sí, es posible. Notemos que nos basta con mostrar una manera de obtener el par [math], pues en tal caso duplicamos dos veces el primer número y una vez el segundo y obtenemos el par [math]. Más aún, como [math], nos alcanza con obtener un par de la forma [math] con [math] y [math], pues en tal caso le podemos restar [math] al número tantas veces como sea necesario para llegar al [math], logrando así el objetivo.
Comenzando con el par [math], duplicamos [math] veces el primer número, obteniendo el par [math], luego hacemos [math] veces la operación de restarle al número más grande el número más chico, obteniendo el par [math], y finalmente duplicamos el segundo número [math] veces. Por el teorema de Fermat-Euler, [math], así que el objetivo está cumplido.
3  
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
Avatar de Usuario
Ivan

Colaborador-Varias
Mensajes: 1023
Registrado: Vie 15 Oct, 2010 7:18 pm
Medallas: 1
Nivel: Exolímpico

Re: Selectivo 16° Cono Sur 2005 - Problema 6

Mensaje sin leer por Ivan »

Spoiler: mostrar
Si [math] con [math] impar, digo que [math] es la parte impar de [math].

Observación: La parte impar del máximo común divisor de [math] y [math] es invariante por las operaciones.

Demostración de la observación: Multiplicar uno de los números por [math] a lo sumo duplica el [math]. Entonces no altera su parte impar.
Restarle un número al otro mantiene igual el [math] y por lo tanto también su parte impar (esto es por el algoritmo de Euclides)[math]

Afirmación: Sea [math] es un número impar. Entonces se puede llegar del par [math] al par [math] [math] la parte impar de [math] es [math].

Notemos que la afirmación prueba que no se puede llegar del par [math] al par [math] y que se puede llegar del par [math] al par [math].

Demostración de la afirmación:
Notemos que [math] es consecuencia inmediata de la afirmación.

Para probar [math] vamos a pensar las operaciones de atrás para adelante. Cambio las operaciones por:
  • Si [math] es par, pasar del par [math] al par [math]
  • Si [math] es par, pasar del par [math] al par [math]
  • Pasar del par [math] al par [math]
  • Pasar del par [math] al par [math]
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 un par [math] con [math] impar. Una vez que probemos esto por la observación sigue lo que queremos.

Algoritmo:
Primero divido por [math] 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]. Notemos que [math] y [math] son impares.
  • Si [math] paso al par [math] y luego a [math]. Si el segundo número sigue siendo par lo divido por hasta que sea impar
  • Si [math] paso al par [math] y luego a [math]. 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], el algoritmo termina y estamos[math]
Guía de $\LaTeX$ (sirve para escribir ecuaciones como $2^{3\times 2}+1=13\cdot 5$)
usuario250

OFO - Jurado-OFO 2015
Mensajes: 222
Registrado: Vie 30 Dic, 2011 12:30 pm
Medallas: 1

Re: Selectivo 16° Cono Sur 2005 - Problema 6

Mensaje sin leer por usuario250 »

Spoiler: mostrar
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).
Responder