Problema 1 Selectivo IMO Rumania 2013

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: 1114
Registrado: Dom 17 Oct, 2010 4:44 pm
Medallas: 8
Nivel: Exolímpico

Problema 1 Selectivo IMO Rumania 2013

Mensaje sin leer por Matías V5 »

Dado un entero [math], sean [math] números enteros tales que [math].
Probar que [math] si y sólo si [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
Squee
Mensajes: 139
Registrado: Lun 05 Dic, 2011 1:55 pm
Nivel: Exolímpico
Ubicación: Bariloche

Re: Problema 1 Selectivo IMO Rumania 2013

Mensaje sin leer por Squee »

Vamos a demostrar la vuelta (o sea la implicacion en sentido derecha a izquierda)
Aclaracion: Arranque usando 3n+2 de natural para la demostracion y despues me di cuenta de lo feo que quedaba, asi que lo cambie por 3d+2=n (asi podia usar el n del enunciado). Espero no haberme olvidado de cambiar ninguno durante el edit.
Pense todos los numeros usando unos determinados numeros combinatorios, pero en realidad si diese vuelta la notacion (por simetria) podrian estar al reves.
O sea:
[math] con lo cual paso a usar un +2. El cual voy a usar en la 2da parte de la demostracion.
Spoiler: mostrar
Primero vamos a demostrar que:[math]
Sea:
n=3d+2
[math]
[math]
El cual siempre es divisible por 3, se ve facilmente contando los multiplos de 3 de la parte de arriba y la de abajo.
Mas analiticamente se podria decir que:
La cantidad de potencias de 3 de [math] es [math]
Y la del [math] es [math], y la suma de ambos es igual o menor a [math]
Asi que a [math] le sobra uno y es multiplo de 3.

Ahora:
[math]
Entonces, para conocer la congruencia de:
[math]
Solo hace falta saber la de
[math]
Que, como esta ultima es divisible por 3 par a par, entonces:
[math]
Los valores posibles de eso son 1 para n par y 2 para n impar.
Vayamos por casos.

[math] si n es par
[math] si n es impar

Multiplicar por -2 en modulo 3, es lo mismo que multiplicar por 1, asi que multiplicar por cualquier potencia de -2 es lo mismo que multiplicar por uno, luego cada elemento de la suma multiplicado por su respectiva potencia de -2 sigue siendo congruente con sigo mismo en el caso de que n sea par, y como
d es par, entonces [math] y como [math]
Queda demostrado lo que necesitabamos.

Si d es impar, entonces [math] y como [math], entonces [math]
Ahora, como multiplicar por -2 no alteraba nada, y tenemos un menos mas adelante de la sumatoria, estamos multiplicando por -1.
Lo cual es lo mismo que multiplicar por 2 cuando se trata de modulo 2, por lo tanto
[math]
Última edición por Squee el Vie 19 Jul, 2013 3:32 pm, editado 5 veces en total.
1  
Squee
Mensajes: 139
Registrado: Lun 05 Dic, 2011 1:55 pm
Nivel: Exolímpico
Ubicación: Bariloche

Re: Problema 1 Selectivo IMO Rumania 2013

Mensaje sin leer por Squee »

Demostracion de la ida (1ra parte de la implicacion):
Spoiler: mostrar
Tanto
[math] (1)
Como
[math] (2)
Son siempre multiplos de 3, por lo tanto se anulan en congruencias modulo 3 y no importa la combinacion lineal que hagamos no vamos a conseguir algo congruente con 1.
La demostracion de (2) ya esta hecha en la parte anterior.
La de (1) es analoga.
Bueno, me quedo un poco desprolijo lleno de edits, pero al menos en papel me parece no haber cometido ningun error.
Responder