FOFO 9 años Problema 5

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
MateoCV

OFO - Medalla de Bronce-OFO 2016 FOFO 6 años - Medalla Especial-FOFO 6 años OFO - Medalla de Oro-OFO 2017 FOFO Pascua 2017 - Medalla-FOFO Pascua 2017 FOFO 7 años - Medalla Especial-FOFO 7 años
OFO - Medalla de Plata-OFO 2018 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019 OFO - Jurado-OFO 2020
COFFEE - Jurado-COFFEE Iván Sadofschi
Mensajes: 242
Registrado: Vie 18 Dic, 2015 12:35 am
Medallas: 11
Nivel: Exolímpico
Ubicación: Córdoba

FOFO 9 años Problema 5

Mensaje sin leer por MateoCV » Jue 10 Oct, 2019 11:29 pm

Decimos que un entero positivo es básico si no existe ningún primo $p\geq 5$ que lo divida. Demostrar que todo entero positivo se puede escribir como la suma de varios números básicos, tales que ninguno de ellos es divisor de otro.
$2^{82589933}-1$ es primo

Avatar de Usuario
MateoCV

OFO - Medalla de Bronce-OFO 2016 FOFO 6 años - Medalla Especial-FOFO 6 años OFO - Medalla de Oro-OFO 2017 FOFO Pascua 2017 - Medalla-FOFO Pascua 2017 FOFO 7 años - Medalla Especial-FOFO 7 años
OFO - Medalla de Plata-OFO 2018 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019 OFO - Jurado-OFO 2020
COFFEE - Jurado-COFFEE Iván Sadofschi
Mensajes: 242
Registrado: Vie 18 Dic, 2015 12:35 am
Medallas: 11
Nivel: Exolímpico
Ubicación: Córdoba

Re: FOFO 9 años Problema 5

Mensaje sin leer por MateoCV » Dom 13 Oct, 2019 8:35 pm

Aquí vamos a publicar la solución oficial
$2^{82589933}-1$ es primo

Avatar de Usuario
Turko Arias

Colaborador-Varias OFO - Medalla de Plata-OFO 2016 OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 COFFEE - Jurado-COFFEE Matías Saucedo
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi
Mensajes: 428
Registrado: Lun 28 Nov, 2011 11:39 am
Medallas: 10
Nivel: Ñandú
Ubicación: La Plata, Provincia de Buenos Aires

Re: FOFO 9 años Problema 5

Mensaje sin leer por Turko Arias » Mar 15 Oct, 2019 12:58 pm

Un clásico
Spoiler: mostrar
El problema lo reescribimos como "Probar que todo entero positivo puede ser escrito como la suma de uno o más enteros positivos de la pinta $2^x3^y$ tales que no haya un término que divida a otro"... Ahora si, manos a la obra:
Vamos a tirar una inducción fuerte para el problema... ¿Qué es una inducción fuerte? Es como una inducción normal pero con esteroides. ¿En qué consiste se preguntarán? En lugar de suponer que algo vale para $n$ y probar entonces que vale para $n+1$, suponemos que vale para TODOS los enteros positivos hasta $n$ y probamos que entonces va a valer para $n+1$. Nuestro caso base trivial es $1=2^03^0$.

Supongamos ahora que el enunciado es cierto hasta un $n$ entero positivo... Vamos a probar que entonces es cierto para $n+1$.

Si $n+1$ es impar, definimos $x$ como el máximo entero positivo tal que $3^x \leq n+1$. Si $n+1$ es potencia de $3$ estamos. Supongamos entonces que $n+1$ no es potencia de $3$, como es impar, $n+1>\frac{n+1-3^x}{2}$ y que encima es entero! Entonces, por nuestra hipótesis inductiva, existen $a_1,...,a_i$ que cumplen el enunciado, es decir $\frac{n+1-3^x}{2}=a_1+...+a_i$ y que no hay dos que se dividan entre ellos. Despejando $n+1$ nos queda $n+1=3^x+2a_1+...+2a_i$. Por nuestra hipótesis, como los $a_j$ no se dividían entre ellos, entonces los $2a_j$ tampoco van a hacerlo. Supongamos que $3^x$ divide a algún $2a_j$, entonces $3^x$ divide a $a_j$, pero entonces, $3^x \leq a_j$, de donde $n+1=3^x+2a_1+...+2a_i \geq 3^x+2a_j \geq 3^x+2.3^x=3^{x+1}$, absurdo por como habíamos definido $x$, luego $3^x$ no divide a ningún $a_j$. Por otro lado, como $2a_j$ es par, nunca va a dividir a $3^x$, luego, si $n+1$ es impar escribimos $n+1=3^x+2a_1+...+2a_i$ y estamos.

Por último, si $n+1$ fuera par, $n+1> \frac{n+1}{2}$ que encima es entero, por lo que podemos escribir $\frac{n+1}{2}=a_1+...+a_i$ con los $a_i$ cumpliendo el enunciado. Despejando nos queda $n+1=2a_1+...+2a_i$, pero claramente si los $a_j$ no se dividían entre ellos, los $2a_j$ tampoco lo hacen... Luego, Nuestra induccionaza está terminada y el problema completo $\blacksquare$
3  
Fundamentalista del Aire Acondicionado

Responder