Ibero 2020 - P4

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 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: 1476
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 8
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Ibero 2020 - P4

Mensaje sin leer por Gianni De Rico »

Demuestre que existe un conjunto $\mathcal{C}$ de $2020$ enteros positivos y distintos que cumple simultáneamente las siguientes propiedades:
  • Cuando se calcula el máximo común divisor de cada dos elementos de $\mathcal{C}$, se obtiene una lista de números todos distintos.
  • Cuando se calcula el mínimo común múltiplo de cada dos elementos de $\mathcal{C}$, se obtiene una lista de números todos distintos.
Esto es trivial por el teorema de Bolshonikov demostrado en un bar de Bielorrusia en 1850

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
Mensajes: 57
Registrado: Mar 31 Dic, 2019 2:26 am
Medallas: 5
Nivel: 3
Ubicación: Rosario, Santa Fe
Contactar:

Re: Ibero 2020 - P4

Mensaje sin leer por Fedex »

Spoiler: mostrar
Si cada par de números $a$, $b$ comparte un divisor primo $p$ que no tiene ningún número más de la lista entonces $p$ divide a $MCD(a, b)$ y no divide a ningún otro $MCD$, por lo que es distinto a cualquiera de estos.
También si cada número tiene un primo $p$ que no tiene ningún otro entonces para un par $a$, $b$ tenemos que el producto $p_a p_b$ de estos primos propios divide a $MCM(a,b)$ y no divide a ningún otro $MCM$ por lo que es distinto a cualquiera.
Como los primos son infinitos conseguimos lo que queremos para cualquier cantidad de números.
3  
$\frac{9}{1^2} \binom{20}{18}$

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 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: 1476
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 8
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Ibero 2020 - P4

Mensaje sin leer por Gianni De Rico »

Dejo una forma de obtener lo que dice @Fedex
Spoiler: mostrar
Reemplazamos $2020$ con un número $n$. Sea $p_k$ el $k$-ésimo número primo. Definimos $P=p_1p_2\ldots p_n$ y consideramos $c_k=\dfrac{P}{p_k}p_{n+k}$ (es decir que $c_k$ tiene todos los primos salvo $p_k$), entonces cada $c_k$ tiene al primo único $p_{n+k}$, y a cada par $(c_i,c_j)$ le faltan los primos $p_i,p_j$ (acá en realidad no es que cada par tiene un primo único, más bien que le faltan primos únicos).
3  
Esto es trivial por el teorema de Bolshonikov demostrado en un bar de Bielorrusia en 1850

Matías

OFO - Medalla de Bronce-OFO 2016 OFO - Medalla de Bronce-OFO 2017 FOFO Pascua 2017 - Medalla-FOFO Pascua 2017 OFO - Medalla de Plata-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años
OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 COFFEE - Mención-COFFEE Ariel Zylber
Mensajes: 205
Registrado: Mar 06 Oct, 2015 7:59 pm
Medallas: 8
Nivel: 3

Re: Ibero 2020 - P4

Mensaje sin leer por Matías »

Spoiler: mostrar
Sean $p_1<p_2<\cdots<p_{4040}$ números primos.
Sea $C=\{a_i|1\leq i\leq 2020\}$ con $a_i=\prod_{k=1}^{i}p_k\prod_{k=2021}^{4041-i}p_k$ $\forall 1\leq i\leq 2020$.
Entonces nos queda que $(a_i:a_j)=\prod_{k=1}^{i}p_k\prod_{k=2021}^{4041-j}p_k$ y $[a_i:a_j]=\prod_{k=1}^{j}p_k\prod_{k=2021}^{4041-i}p_k$ $\forall 1\leq i\leq j\leq 2020$, así que los dcm y los mcm son todos distintos.
2  

Avatar de Usuario
Emerson Soriano

OFO - Mención-OFO 2015 OFO - Medalla de Oro-OFO 2016 OFO - Medalla de Plata-OFO 2017 OFO - Medalla de Bronce-OFO 2018 OFO - Mención-OFO 2020
Mensajes: 801
Registrado: Mié 23 Jul, 2014 10:39 am
Medallas: 5

Re: Ibero 2020 - P4

Mensaje sin leer por Emerson Soriano »

Esta solución me la contaron, me pareció muy buena.
Spoiler: mostrar
Sabemos que hay $2020$ números de la forma $2^k\cdot 3^{2019-k}$, donde $k$ es un entero tal que $0\leq k\leq 2019$. No es difícil probar que estos $2020$ números cumplen.
1  

Hernan26

OFO - Medalla de Plata-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 FOFO 9 años - Medalla Especial-FOFO 9 años OFO - Medalla de Oro-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020
COFFEE - Mención-COFFEE Ariel Zylber
Mensajes: 26
Registrado: Sab 08 Dic, 2018 5:51 pm
Medallas: 6
Nivel: 3
Ubicación: Uruguay

Re: Ibero 2020 - P4

Mensaje sin leer por Hernan26 »

Otro ejemplo:
Spoiler: mostrar
Si el conjunto $C_k=\{a_1,a_2,...,a_k\}$ cumple la condición del enunciado, entonces el conjunto
$C_{k+1}=\{H_1,H_2,...,H_k, \prod_{l=1}^{l=k}(a_l^l) \cdot q\cdot p^{k+1}\}$
Con $H_i=p^i\cdot q^{i+1}\cdot a_i^{k+1}$ para todo $1\leq i\leq k$ y con $p,q$ primos distintos coprimos con todos los $a_i$ del conjunto $C_k$, también cumple lo que pide el enunciado.
Con inducción el problema se termina.

Responder