Nacional 2022 - Nivel 1 - Problema 2

Avatar de Usuario
Monazo

OFO - Medalla de Plata-OFO 2017 OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Mención-FOFO Pascua 2019 FOFO 9 años - Jurado-FOFO 9 años 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
FOFO 10 años - Jurado-FOFO 10 años OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022
Mensajes: 371
Registrado: Dom 14 Sep, 2014 2:30 pm
Medallas: 15
Nivel: Exolímpico

Nacional 2022 - Nivel 1 - Problema 2

Mensaje sin leer por Monazo »

Melina escribió en el pizarrón cuatro números enteros positivos distintos y, a continuación, calculó el máximo común divisor de cada pareja formada por dos es esos cuatro números. Obtuvo así seis resultados distintos: $1$, $2$, $3$, $4$, $5$ y $N$, con $N>5$. Determinar el menor valor posible de $N$.

Nota: Dado dos números enteros $a$ y $b$, el máximo común divisor de $a$ y $b$ es el mayor entero positivo $d$ tal que $d$ divide a $a$ y $d$ divide a $b$.
Soy una Estufa en Piloto
:shock:
Fedex

COFFEE - Mención-COFFEE Matías Saucedo OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Medalla-FOFO Pascua 2020 COFFEE - Mención-COFFEE Ariel Zylber COFFEE - Mención-COFFEE Iván Sadofschi
FOFO 10 años - Medalla-FOFO 10 años OFO - Medalla de Plata-OFO 2021 OFO - Jurado-OFO 2022
Mensajes: 189
Registrado: Mar 31 Dic, 2019 2:26 am
Medallas: 8
Nivel: 3
Ubicación: Rosario, Santa Fe
Contactar:

Re: Nacional 2022 - Nivel 1 - Problema 2

Mensaje sin leer por Fedex »

Spoiler: mostrar
Lema: Si en la lista de $MCD$ aparecen al menos dos números que son divisibles por $d$ entonces hay al menos tres.

Demostración: Recordemos que $d |mcd(a,b)$ sí y solo sí $d|a$ y $d|b$. Ahora si hay al menos dos $MCD$ que son divisibles por $d$ hay al menos tres números del pizarrón que son divisibles por $d$, por lo que hay al menos $\binom{3}{2} = 3$ $MCD$ que lo son.

Vamos con el problema. Notemos que $N$ es par porque aparecen el $2$ y el $4$ y tiene que haber un tercero. Además, $N$ no es divisible por $d = 3, 4, 5$ ya que si lo fuera, aparecerían al menos dos números divisibles por $d$ pero no tres, lo que contradice el lema.

El primer $N>5$ que verifica todo esto es $N = 14$ donde un ejemplo que funciona son los números $20, 15, 28, 42$. Finalmente concluimos que el menor es $N = 14$.
1  
This homie really did 1 at P6 and dipped.
Responder