Iberoamericana 2021 - Problema 1

Problemas que aparecen en el Archivo de Enunciados.
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: 1131
Registrado: Dom 17 Oct, 2010 4:44 pm
Medallas: 8
Nivel: Exolímpico

Iberoamericana 2021 - Problema 1

Mensaje sin leer por Matías V5 »

Sea $P=\{p_1,p_2,\ldots ,p_{10}\}$ un conjunto de $10$ primos distintos y sea $A$ el conjunto de todos los enteros mayores que $1$ tales que en su descomposición en factores primos aparecen únicamente primos de $P$. Los elementos de $A$ se colorean de tal forma que:

a) cada elemento de $P$ tiene un color distinto,
b) si $m,n\in A$, entonces $mn$ tiene el mismo color de $m$ o $n$,
c) para cualquier par de colores distintos $\mathcal{R}$ y $\mathcal{S}$, no existen $j,k,m,n\in A$ (no necesariamente distintos), con $j,k$ de color $\mathcal R$ y $m,n$ de color $\mathcal S$, tales que $j$ divide a $m$ y $n$ divide a $k$, simultáneamente.

Demuestre que existe un primo de $P$ tal que todos sus múltiplos en $A$ tienen el mismo color.
1  
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
Avatar de Usuario
Sandy

OFO - Medalla de Bronce-OFO 2019 OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 COFFEE - Mención-COFFEE Ariel Zylber FOFO 10 años - Copa-FOFO 10 años
OFO - Medalla de Oro-OFO 2021 FOFO 11 años - Medalla-FOFO 11 años OFO - Medalla de Plata-OFO 2022 OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024 FOFO 14 años - Jurado-FOFO 14 años
Mensajes: 303
Registrado: Lun 27 Nov, 2017 1:59 am
Medallas: 12
Nivel: 3

Re: Iberoamericana 2021 - Problema 1

Mensaje sin leer por Sandy »

Spoiler: mostrar
Veamos primero por inducción en la cantidad de factores primos (no necesariamente distintos) que hay sólo $10$ colores. Cuando la cantidad de factores es $1$ es claro (pues son los $10$ primos). Si tenemos que para $t$ factores vale, sea $n=p_ik$ de $t+1$ factores. Debe ser por la condición b) que es o del color de $p_i$ o del de $k$, es decir de uno de los $10$ o de uno de los $10$ (por hipótesis inductiva).
Ahora, sea sin pérdida de generalidad $p_1$ el primo con el mismo color que $p_1\times p_2\times ...\times p_{10}$. Supongamos que hay un múltiplo $a$ de $p_1$ con distinto color que $p_1$, sin pérdida de generalidad del mismo que $p_2$. Luego $p_1\mid a$ y $p_2\mid p_1\times p_2\times ...\times p_{10}$, lo que contradice la condición c). Luego $p_1$ tendrá todos sus múltiplos de su color como buscábamos.
2  
Fallo inapelable.
Goku_Master
Mensajes: 8
Registrado: Lun 01 Ene, 2024 9:43 pm
Nivel: 2

Re: Iberoamericana 2021 - Problema 1

Mensaje sin leer por Goku_Master »

Spoiler: mostrar
Para resolver este problema utilizare los siguiente 2 lemas:
Lema 1: Si un nùmero $m_{1} ∈ A$ tiene un color $M$ pero ninguno de sus multiplos tiene el mismo color entonces $∃$ un numero $m_{2} ∈ A$ que tendra el mismo color de uno de los multiplos de $m_{1}$

Lema 2: $∀$ $n ∈ A$ Con n compuesto $∃$ $p_i ∈ P$ tal que $n$ y $p_i$ tengan el mismo color

Ahora sea $p_j ∈ P$ de color $J$ y $a = p_jk$ con $k ∈ A$ y $p_j$ no divide a $k$, de color $K$. Ahora por el lema 1 y el lema 2 podemos hacer la siguiente suposición $m = \prod_{u=1}^{n} (p_u)$ donde $m$ es de color $J$. Ahora por el lema 2 $∃$ $p_{k} ∈ P$ que tendra el mismo color que $a$, pero notemos que llegamos a un absurdo ya que $p_j \mid n$ y $p_k \mid m$ rompiendo la propiedad c-), por lo que $n$ es del mismo color que $p_j$ ya que $p_j$ y $p_k$ tienen diferentes colores. Luego como $a$ son todos los multiplos de $p_j$ llegamos a que $∃$ un primo de $P$ tal que todos sus multiplos en $A$ son del mismo color.

Prueba lema 1:
Spoiler: mostrar
Supongamos que existe un numero $b ∈ A$ tal que ninguno de sus multiplos tiene el mismo color. sea $B$ un subconjunto de $A$ donde estan todos los multiplos de $b$ como los elementos de $B$ deben ser compuestos (ya que deben ser multiplos de $B$) solo aplicamos la propiedad a-) y entonces $∃$ un numero $c ∈ A$ que tendra el mismo color de uno de los elementos de $B$ terminando asi la prueba
Prueba lema 2:
Spoiler: mostrar
Este lema es basicamente el resultado de aplicar reiteradas veces la propiedad a-), ya que si existe un numero $n$ compuesto de color $N$ este se podra factorizar y debido a la propiedad a-) alguno de los 2 factores debe tener el color $N$, como $n$ tiene finitos factores primos habra un momento donde solo queden 2 factores primos y entonces alguno de ellos tendra el color $N$ completando de esa forma la prueba
Responder