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 COFFEE - Jurado-COFFEE Ariel Zylber
Mensajes: 400
Registrado: Dom 26 Oct, 2014 8:30 pm
Medallas: 12
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 COFFEE - Jurado-COFFEE Ariel Zylber
Mensajes: 400
Registrado: Dom 26 Oct, 2014 8:30 pm
Medallas: 12
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 cuyos extremos son puntos de $X$, 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. Que haya un camino que empieza en $A$ y termina en $B$ quiere decir que hay una sucesión finita de segmentos azules de modo que cada segmento termina donde empieza el siguiente, el primer segmento empieza en $A$, y el último segmento termina en $B$.
1  

Avatar de Usuario
Turko Arias

Colaborador-Varias OFO - Medalla de Plata-OFO 2016 OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 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: 429
Registrado: Lun 28 Nov, 2011 11:39 am
Medallas: 10
Nivel: Ñandú
Ubicación: La Plata, Provincia de Buenos Aires

Re: Maratón de Problemas

Mensaje sin leer por Turko Arias » Dom 31 May, 2020 9:54 pm

No quiero arruinar la emoción :o :o :o
Pero técnicamente es a lo sumo el Problema 359, porque:
Nacho escribió:
Lun 06 May, 2013 9:10 pm

Problema 101:

Hallar todas las funciones $f:\mathbb{R}\to\mathbb{R}$ tales que $$f(x+y)+y\leq f(f(f(x)))$$ vale para todos $x,y\in\mathbb{R}$.

Y
MateoCV escribió:
Lun 22 Ago, 2016 9:56 pm
Problema 208
Encontrar todas las funciones $f:\mathbb{R} \to \mathbb{R}$ tales que

$f(x+y)+y\leq f(f(f(x)))$

$\forall x, y \in \mathbb{R}$
Fundamentalista del Aire Acondicionado

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: 800
Registrado: Mié 23 Jul, 2014 10:39 am
Medallas: 5

Re: Maratón de Problemas

Mensaje sin leer por Emerson Soriano » Sab 11 Jul, 2020 1:57 am

jujumas escribió:
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.
No se entiende bien el enunciado. ¿Los segmentos azules que se trazan comienzan y terminan en puntos de $X$? Cuando dice que un camino comienza en $A$ y termina en $B$, se refiere a que hay una secuencia de segmentos azules tal que el primer segmento azul comienza en $A$ y el último segmento azul termina en $B$? Sería bueno que se aclare o se definan bien estas cositas para que haya un mayor entendimiendo =). Saludos.

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 COFFEE - Jurado-COFFEE Ariel Zylber
Mensajes: 400
Registrado: Dom 26 Oct, 2014 8:30 pm
Medallas: 12
Nivel: Exolímpico

Re: Maratón de Problemas

Mensaje sin leer por jujumas » Mar 14 Jul, 2020 6:26 pm

Emerson Soriano escribió:
Sab 11 Jul, 2020 1:57 am
jujumas escribió:
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.
No se entiende bien el enunciado. ¿Los segmentos azules que se trazan comienzan y terminan en puntos de $X$? Cuando dice que un camino comienza en $A$ y termina en $B$, se refiere a que hay una secuencia de segmentos azules tal que el primer segmento azul comienza en $A$ y el último segmento azul termina en $B$? Sería bueno que se aclare o se definan bien estas cositas para que haya un mayor entendimiendo =). Saludos.
Si a ambas preguntas. Ahí arreglo!

Responder