Maratón de Problemas

jujumas

OFO - Mención-OFO 2015 OFO - Medalla de Plata-OFO 2016 FOFO 6 años - Medalla Especial-FOFO 6 años OFO - Oro perfecto-OFO 2017 FOFO Pascua 2017 - Medalla-FOFO Pascua 2017
FOFO 7 años - Medalla Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2018 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019
OFO - Jurado-OFO 2020
Mensajes: 399
Registrado: Dom 26 Oct, 2014 8:30 pm
Medallas: 11
Nivel: Exolímpico

Re: Maratón de Problemas

Mensaje sin leer por jujumas » Sab 02 May, 2020 3:48 am

Solución 359
Spoiler: mostrar
Para $n=1$ el problema es mentira así que lo demostramos para $n$ mayor a $1$. Vamos a hacer inducción.

Si $n=2$, los únicos $p$ y $q$ que cumplen todas las condiciones son $p=1$ y $q=2$ (basta pedir que cumplan $1 \leq p < q \leq 2$ para descartar los otros casos).

Supongamos ahora que la sumatoria da $\frac{1}{2}$ para $n=k-1$. Notemos que al calcular la sumatoria para $n=k$, estamos agregando las fracciones $\frac{1}{pq}$ con $p$ y $q$ coprimos que cumplen $q=k$, y estamos sacando las que antes cumplían $p+q=k$. Luego, basta demostrar que:

$$ \sum_{(p:k)=1; 1\leq p < k} \frac{1}{pk} = \sum_{(p:q)=1; 1\leq p < q \leq k; p + q = k} \frac{1}{pq} $$

pero la segunda sumatoria se puede escribir como:

$$\sum_{(p:q)=1; 1\leq p < k/2} \frac{1}{p(k-p)}$$.

Y como por eculides tenemos que $(p:q) = 1$ si y solo si $(p:q+p) = (p:k) = 1$, tenemos que esto último es:

$$\sum_{(p:k)=1; 1\leq p < k/2} \frac{1}{p(k-p)}$$.

Ahora, notemos que $p$ no puede ser $k/2$, ya que o bien $k/2$ no es entero, o es un divisor de $k$, que nunca sería coprimo con $k$ a menos que sea $1$, pero estamos trabajando con $k$ al menos $3$. Luego,

$$ \sum_{(p:k)=1; 1\leq p < k} \frac{1}{pk} = \sum_{(p:k)=1; 1\leq p < k/2} \frac{1}{pk} + \sum_{(p:k)=1; 1\leq p > k/2} \frac{1}{pk}$$.

Además, en esta descomposición en dos sumatorias, si $\frac{1}{pk}$ es sumando en una sumatoria, tenemos que $\frac{1}{(k-p)k}$ es sumando en la otra sumatoria, ya que si $p < k/2$, $k-p > k/2$, y si $(p:k) = 1$, $(-p:k)=1$ y por euclides, $(k-p:k)=1$. Luego, tenemos que la primera sumatoria no es más que:

$$ \sum_{(p:k)=1; 1\leq p < k/2} \frac{1}{pk} + \frac{1}{(k-p)k}$$.

Pero $\frac{1}{pk} + \frac{1}{(k-p)k} = \frac{1}{k} (\frac{1}{p} + \frac{1}{(k-p)}) = \frac{1}{k} (\frac{p+k-p}{p(k-p)}) = \frac{1}{p(k-p)}$, y la primer sumatoria es igual a la segunda, listo.

jujumas

OFO - Mención-OFO 2015 OFO - Medalla de Plata-OFO 2016 FOFO 6 años - Medalla Especial-FOFO 6 años OFO - Oro perfecto-OFO 2017 FOFO Pascua 2017 - Medalla-FOFO Pascua 2017
FOFO 7 años - Medalla Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2018 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019
OFO - Jurado-OFO 2020
Mensajes: 399
Registrado: Dom 26 Oct, 2014 8:30 pm
Medallas: 11
Nivel: Exolímpico

Re: Maratón de Problemas

Mensaje sin leer por jujumas » Sab 02 May, 2020 4:01 am

En honor a que $360$ es un número algo especial, les tiro uno de mis problemas de olimpíadas favoritos entre los que pensé el año pasado. Dado que el problema fue tomado en un simulacro, pido abstenerse a responder a quienes ya rindieron el problema (o por lo menos a quienes ya conocen su solución).

Problema 360:
Sea $X$ el conjunto de todos los puntos $(x,y)$ del plano cuyas dos coordenadas son enteras. Supongamos que se trazan segmentos con color azul de modo que dados cualesquiera dos puntos $A$ y $B$ en $X$, hay exactamente un camino que empieza en $A$ y termina en $B$ formado por segmentos azules.
Demostrar que existen dos puntos de $X$ que están a distancia $1$ entre sí y la longitud del camino de segmentos azules que los conecta (es decir, la suma de las longitudes de todos los segmentos del camino) es mayor que $10^{360}$.

Aclaración: Si $PR$ es un segmento azul que contiene en su interior un punto $Q$ de $X$, entonces no necesariamente ocurre que $PQ$ se considere uno de los segmentos azules trazados.
1  

Responder