Nacional 2022 - Nivel 1 - Problema 2

Problemas que aparecen en el Archivo de Enunciados.
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
OFO - Jurado-OFO 2023 OFO - Jurado-OFO 2024
Mensajes: 381
Registrado: Dom 14 Sep, 2014 2:30 pm
Medallas: 17
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 OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 269
Registrado: Mar 31 Dic, 2019 2:26 am
Medallas: 11
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.
Avatar de Usuario
FelipeGigena

OFO - Mención-OFO 2023 OFO - Mención-OFO 2024
Mensajes: 27
Registrado: Vie 13 May, 2022 8:29 pm
Medallas: 2
Nivel: 2

Re: Nacional 2022 - Nivel 1 - Problema 2

Mensaje sin leer por FelipeGigena »

Spoiler: mostrar
Si un número

Sean $A$, $B$, $C$ y $D$ los $4$ números:
Notemos que en la lista de resultados de los $mcd$ están el $4$ y el $2$. Esto significa que hay dos números en los cuales aparecen dos factores $2$ y un tercero en el cual aparece un único $2$:

$A = 2 * 2$
$B = 2 * 2$
$C = 2$

Notar ahora que en $D$ no puede aparecer ningún factor $2$. De lo contrario, todos los resultados de los $mcd$ serían números pares.
Tenemos "ubicados" dos de los seis $mcd$: El $4$ y el $2$. Ahora nos quedaría ver donde se ubican $1$, $3$, $5$ y $N$.

Si hay un $mcd(x, y) = 3$; $3$ va a tener que estar en $D$. $mcd(A, B, C) = 2$, por lo que si agregamos factores $3$ a dos de esos números nunca obtendremos un $mcd(x, y) = 3$, que es lo que estamos buscando.

Utilizamos el mismo argumento para el $5$, nos queda:

$A = 2 * 2$
$B = 2 * 2$
$C = 2$
$D = 5 * 3$

Como sabemos que $D$ no posee ningún factor $2$, este tendrá como resultado en los $mcd$ que participe al $1$, $3$ y $5$. Esto lo podemos ver en que los demás números tienen en común al menos un $2$, por lo que el único que nos queda para los resultados impares es $D$.

Ahora intentemos ubicar a todos los $mcd$: vamos a decir que el $2$ por conveniencia es el $mcd$ entre $A$ y $C$. Podríamos hacerlo también entre $B$ y $C$, pero como por ahora son el mismo número, no importa. Tenemos lo siguiente:

$mcd(A, B) = 4$
$mcd(A, C) = 2$
$mcd(B, C) = 2$

El $mcd$ entre $B$ y $C$ debe ser mayor a $2$, pues ya hemos ubicado el $2$ como el $mcd$ entre $A$ y $C$. Sabemos también que ni $C$ ni $B$ pueden incluir mutuamente ni al $3$ ni al $5$, si lo hiciesen, habrían dos resultados de los $mcd$ de $D$ con el mismo factor (no puede ser porque antes vimos que los $mcd$ que incluyen a $D$ son $1$, $3$, y $5$; coprimos dos a dos). Teniendo en cuenta esto, el menor primo mayor que $3$ y $5$ que nos queda agregar a $B$ y a $C$ es $7$:

$A = 2 * 2$
$B = 2 * 2 * 7$
$C = 2 * 7$
$D = 5 * 3$

Ahora nos queda agregar un factor $5$ y un factor $3$ a cualquier número distinto de $D$:

$A = 2 * 2 * 3$
$B = 2 * 2 * 7$
$C = 2 * 7 * 5$
$D = 5 * 3$

Finalmente, tenemos:

$mcd(B, D) = 1$
$mcd(A, C) = 2$
$mcd(A, D) = 3$
$mcd(A, B) = 4$
$mcd(C, D) = 5$
$mcd(B, C) = 14$

Por lo que el menor valor posible de $N$ es $14$.
MEDIO EQUILÁTERO?
Avatar de Usuario
Ulis7s

OFO - Mención-OFO 2024
Mensajes: 183
Registrado: Dom 07 May, 2023 1:13 pm
Medallas: 1
Nivel: 1
Ubicación: La Pampa

Re: Nacional 2022 - Nivel 1 - Problema 2

Mensaje sin leer por Ulis7s »

$Solución:$
Spoiler: mostrar
Veamos que hay $2$ $mcd$ pares, luego siempre hay otro mas, con esto justifico que $N$ es par, veamos que para que N sea mayor que $5$ debe tener al $3$, al $5$, al $7$, o algun otro primo mayor. Veamos que si tiene al $3$, $N=6$. Luego hay $3$ números que tienen al $3$ en su descomposición. Entonces hay $3$ que tienen un $3$ y entonces hay $3$ mcd que son divisibles por $3$, Absurdo! El mismo absurdo se repite de manera análoga para $N=10$ ya que nos dice que habrá $3$ múltiplos de $5$. Luego el mínimo $N$ se da para $N=14$ donde un ejemplo son los números:
$20,28,42,15$
We needed 5 more more points!! :roll: @ulisess.kr
Responder