OFO 2019 Problema 11

lucasdeamorin

FOFO 6 años - Medalla Especial OFO - Jurado FOFO 8 años - Jurado
Mensajes: 74
Registrado: Dom 22 Dic, 2013 9:17 pm
Medallas: 4
Nivel: Otro

OFO 2019 Problema 11

Mensaje sin leer por lucasdeamorin » Dom 20 Ene, 2019 12:02 am

Sea $C$ un conjunto infinito de enteros positivos donde todo elemento es divisible por al menos un primo mayor a $10^{100}$, pruebe que existe un subconjunto infinito $S$ de $C$ tal que cualquier suma finita de elementos distintos de $S$ tenga al menos un factor primo mayor a $10^{100}$.
1  
Si X tiende a [math], [math] se seca.

lucasdeamorin

FOFO 6 años - Medalla Especial OFO - Jurado FOFO 8 años - Jurado
Mensajes: 74
Registrado: Dom 22 Dic, 2013 9:17 pm
Medallas: 4
Nivel: Otro

Re: OFO 2019 Problema 11

Mensaje sin leer por lucasdeamorin » Lun 28 Ene, 2019 1:21 am

Spoiler: mostrar
Llamemos $c_1<c_2<\ldots $ a los elementos de $C$ y $m_0<m_1<m_2<\ldots$ a los números cuyos divisores primos son menores o iguales a $10^{100}$.
También llamemos $maxI$ al máximo de un conjunto $I$.

Por hipótesis, para todo $n$ existe $k_n$ tal que $m_{k_n}<c_n<m_{k_n+1}$.

Si sucediera que $c_0+c_1+c_2+\ldots +c_n<m_{k_n+1}$ para todo $n$ ya ganaríamos, en efecto, para cualquier conjunto de indices $I$:

$$m_{k_{max I}}<c_{max I}\leq \sum_{i\in I}c_i \leq c_1+c_2+\ldots +c_{max I}<m_{k_{max I}+1}$$

Se sigue que si $m_{k_n+1}-c_n$ toma valores arbitrariamente grandes podríamos quedarnos con infinitos elementos de $C$ y estar en la situación anterior y ganar.
Supongamos que esto no pasa, es decir, que $m_{k_n+1}-c_n$ esta acotado.
Por palomar, se sigue que para alguna constante $C_0$ e infinitos $n$ tales que $m_{k_n+1}-c_n=C_0$.
Quedándonos con dichos $n$ podemos suponer que $m_{k_n+1}-c_n=C_0$ para todo $n$. Además, también podemos suponer que $c_1>C_0$ (eliminando a lo mas $C_0$ elementos de $C$).

Hagamos el mismo razonamiento otra vez:
Si sucediera que $c_0+c_1+\ldots +c_n<m_{k_n+2}$ para todo $n$ ya ganaríamos, para cualquier conjunto de indices $I$ con al menos dos elementos tendríamos:

$$m_{k_{max I}+1}=c_{max I}+C_0<c_{max I}+c_1\leq \sum_{i\in I}c_i \leq c_1+c_2+\ldots +c_{max I}<m_{k_{max I}+2}$$

Se sigue que si $m_{k_n+2}-m_{k_n+1}$ toma valores arbitrariamente grandes podríamos quedarnos con infinitos elementos de $C$ y estar en la situación anterior y ganar.
Si esto no pasara, $m_{k_n+2}-m_{k_n+1}$ estaría acotado y, por palomar, existirían una constante $C_1$ e infinitos $n$ para los cuales $m_{k_n+2}-m_{k_n+1}=C_1$.
Podemos suponer que $m_{k_n+2}-m_{k_n+1}=C_1$ para todo $n$. Además, también podemos suponer que $c_1$ es mayor que $C_0$ y $C_1$.

Repitiendo esto $10^{100}$ veces, o bien ganamos en algún paso o bien obtenemos un conjunto infinito $C$ y ciertas constantes $C_0,C_1,\ldots ,C_{10^{100}+1}$ tales que para todo $n$:
  • $m_{k_n+1}-c_n=C_0$.
  • $m_{k_n+l+1}-m_{k_n+l}=C_l$ para todo $l=1,2,\ldots, 10^{100}+1$.

Veamos que el segundo caso no puede ocurrir:

Para cada primo $p\leq 10^{100}$, sea $e(p)=max\{v_p(C_l+C_{l+1}+\ldots+C_{r}): 1\leq l\leq r\leq 10^{100}+1 \}$.
Para cada $n$, a lo sumo existe un $l$ entre $1$ y $10^{100}+1$ tal que $v_p(m_{k_n+1})>e(p)$. En efecto, si existieran $l<l'$ con dicha condición, $$e(p)<v_p(m_{k_n+l'}-m_{k_n+l})=v_p(C_l+C_{l+1}+\ldots +C_{l'-1})\leq e(p)$$
lo cual es claramente absurdo.
Como la cantidad de primos menor o iguales a $10^{100}$ es a lo sumo $10^{100}$, se sigue que para cada $n$ existe un $l_n$ entre $1$ y $10^{100}+1$ tal que $v_p(m_{k_n+l_n})\leq e(p)$ para cada primo $p\leq 10^{100}$.
Pero entonces, para todo $n$,$$0<c_n<m_{k_n+l_n}\leq \prod_{\textrm{primo }p\leq 10^{100}}p^{e(p)}$$
lo que contradice que $C$ sea infinito dado que el lado derecho es una constante finita que no depende de $n$.
Si X tiende a [math], [math] se seca.

Responder