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: 401
Registrado: Dom 26 Oct, 2014 8:30 pm
Medallas: 12
Nivel: Exolímpico

Re: Maratón de Problemas

Mensaje sin leer por jujumas »

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: 401
Registrado: Dom 26 Oct, 2014 8:30 pm
Medallas: 12
Nivel: Exolímpico

Re: Maratón de Problemas

Mensaje sin leer por jujumas »

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
FOFO 10 años - Jurado-FOFO 10 años
Mensajes: 477
Registrado: Lun 28 Nov, 2011 11:39 am
Medallas: 11
Nivel: Ñandú
Ubicación: La Plata, Provincia de Buenos Aires

Re: Maratón de Problemas

Mensaje sin leer por Turko Arias »

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

Re: Maratón de Problemas

Mensaje sin leer por Emerson Soriano »

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: 401
Registrado: Dom 26 Oct, 2014 8:30 pm
Medallas: 12
Nivel: Exolímpico

Re: Maratón de Problemas

Mensaje sin leer por jujumas »

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!

Avatar de Usuario
jhn

OFO - Medalla de Plata-OFO 2018
Mensajes: 520
Registrado: Mié 10 Oct, 2012 3:25 pm
Medallas: 1
Nivel: Otro
Ubicación: Venezuela

Re: Maratón de Problemas

Mensaje sin leer por jhn »

Sería bueno que cuando un problema tenga uno o dos meses sin que nadie envíe una solución, el proponente postee la solución y proponga otro problema, no les parece?
Todo problema profana un misterio; a su vez, al problema lo profana su solución.

sebach

Colaborador-Varias OFO - Medalla de Bronce-OFO 2017 OFO - Medalla de Bronce-OFO 2018 OFO - Medalla de Bronce-OFO 2020
Mensajes: 153
Registrado: Dom 06 Mar, 2011 11:49 am
Medallas: 4
Nivel: Exolímpico

Re: Maratón de Problemas

Mensaje sin leer por sebach »

Sí totalmente, ya se había hablado de eso. Supongo que lo que pasó es que como nadie posteaba nada, quien posteó el último problema colgó 100% , que puede pasar.
Buenísimo revivirlo para que esa persona lo vea y cambie de problema (o aparezca alguien que lo resuelva antes)

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: 401
Registrado: Dom 26 Oct, 2014 8:30 pm
Medallas: 12
Nivel: Exolímpico

Re: Maratón de Problemas

Mensaje sin leer por jujumas »

Bueno, vamos a revivir la maratón.

Solución 360:
Spoiler: mostrar
Notemos que la condición de camino único se traduce a que el grafo formado por los lattice con segmentos azules por aristas es un árbol. Usaremos repetidas veces que si le sacamos un arista a un árbol entonces el árbol queda separado en exactamente dos componentes conexas. Supongamos que lo que queremos demostrar no es cierto.


Lema: No hay ningún segmento azul de longitud mayor a $10^{360}$.
Demo: Supongamos que lo hay. Luego, sacando el segmento azul que mide esto, el árbol queda dividido en dos componentes conexas no vacías y es claro que existen dos puntos a distancia $1$ en el plano que están en componentes opuestas, digamos $X$ e $Y$. Luego, el único camino que une $X$ e $Y$ utiliza el segmento azul, y por lo tanto mide más de $10^{360}$.


Luego, de existir contraejemplo, tenemos que todos los segmentos en el árbol tienen longitud menor a una constante $K$.


Lema: Para todo entero positivo $N$, existen dos vértices del grafo $u$ y $v$ tales que el camino entre $u$ y $v$ tiene más de $N$ aristas.
Demo: Tomar dos puntos $u$ y $v$ a distancia mayor a $NK$ en el plano y usar el lema anterior.


Lema: Para todo entero positivo $M$, existen dos vértices $a$ y $b$ conectados por un arista en el árbol tal que de remover el arista que los une, el árbol es separado en dos componentes conexas de al menos $M$ vértices cada una.
Demo: Basta tomar un camino de $2M+1$ aristas entre dos vértices del árbol, que sabemos existe por el lema anterior, y tomar $ab$ como el arista del medio.


Tomemos $a$ y $b$ como en el último lema. Notemos que la circunferencia $\omega$ de centro $a$ y radio $10^{360}$ contiene un número finito $m$ de vértices del árbol. Tomando entonces $M>m$, tenemos que existen puntos en ambas componentes conexas afuera de $\omega$. Sean $e$ y $f$ estos puntos, es facil ver que existe una sucesión de puntos $x_1$, $x_2$, $\ldots$, $x_n$ tales que $x_1=e$, $x_n=f$, ningún $x_i$ está en $\omega$, y $x_i$ y $x_{i+1}$ están a distancia $1$ en el plano para todo $i$. Luego, como $x_1$ y $x_n$ están en componentes conexas distintas, existe $j$ tal que $x_j$ y $x_{j+1}$ están en componentes conexas distintas.


Finalmente, tomando $x=x_j$, $y=x_{j+1}$, tenemos que $x$ e $y$ están a distancia $1$ entre sí y el único camino que los une implica recorrer el arista $ab$, y luego implica moverse del vértice $x$ al vértice $a$, pero ya sabemos que para hacer esto tenemos que movernos al menos $10^{360}$ unidades por segmentos azules pues $x$ está afuera de $\omega$.


Esto revive la maratón.
Problema 361:
Hallar todas las parejas de enteros positivos $(m,n)$ tales que $mn+1=n^2+m$.

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
Mensajes: 203
Registrado: Lun 27 Nov, 2017 1:59 am
Medallas: 5
Nivel: 3

Re: Maratón de Problemas

Mensaje sin leer por Sandy »

Solución 361
Spoiler: mostrar
$mn+1=n^2+m\Longleftrightarrow m(n-1)=n^2-1=(n+1)(n-1)$
Esto implica que, o bien $n-1=0$ y entonces $n=1$, o bien $m=n+1$.
Verifiquemos que ambas funcionen:
$n=1, m\in \mathbb{N}$: $mn+1=m+1=1^2+m=n^2+m$
$m=n+1, n\in \mathbb{N}$: $mn+1=(n+1)n+1=n^2+n+1=n^2+m$.
Luego las parejas que cumplen son $(m,n)=(m,1)$ y $(m,n)=(n+1, n)$
Problema 362
En un concierto cantan $6$ cantantes $c_1, c_2, ..., c_{6}$. Para cada cantante $c_i$, o bien quiere cantar justo después de otro cantante $c_j$ ($j\neq i$), o bien $c_i$ no tiene ningún tipo de preferencia. Determinar los posibles valores de $n$ tal que hay exactamente $n$ maneras de ordenar a los cantantes sin que quede ninguno insatisfecho.
$u=tan\left(\frac{x}{2}\right)$
$\frac{2}{1+u^2}du=dx$

Avatar de Usuario
NicoRicci

OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 COFFEE - Mención-COFFEE Ariel Zylber
Mensajes: 36
Registrado: Lun 08 Oct, 2018 2:31 pm
Medallas: 3
Nivel: 2

Re: Maratón de Problemas

Mensaje sin leer por NicoRicci »

Solución 362
No se si está bien
Spoiler: mostrar
Denotamos $c_a \leftarrow c_b$ cuando el cantante $c_b$ quiere cantar después de $c_a$
Llamamos cadena a algunos cantantes que quieren cantar uno después del otro, de esta forma: $c_a \leftarrow c_b \leftarrow c_c (...) \leftarrow c_f$ (no necesariamente tienen que ser $6$, pueden ser cualquier valor entero del $1$ al $6$ inclusive)
Es claro que si hay una manera de ordenar a los cantantes de manera que queden satisfechos, significa que dos cantantes no pueden querer cantar después de uno solo, por ende los cantantes están divididos en cadenas
Luego, los cantantes están divididos de la siguiente forma:
$c_a$ $c_b$ $c_c$ $c_d$ $c_e$ $
c_f$, y entre cada dos de éstos números (seguidos) o bien hay una flecha o bien no hay una flecha, situación a la cual vamos a llamar barrera. Por ejemplo:
$c_a \leftarrow c_b | c_c \leftarrow c_d \leftarrow c_e | c_f$
Ahora, para que los cantantes no queden insatisfechos necesitamos que las cadenas se respeten, es decir, cada cadena contarla como "un solo cantante" (un solo elemento); luego, si hay $k$ barreras, hay $k+1$ cadenas, por ende la cantidad de formas de ordenar esas cadenas que son distintas entre si es $(k+1)!$
La cantidad de barreras puede variar de $0$ a $5$ inclusive, por ende $n$ puede ser $1$, $2$, $6$, $24$, $120$ o $720$
Como ejemplos:
$n = 1$______$c_1 \leftarrow c_2 \leftarrow c_3 \leftarrow c_4 \leftarrow c_5 \leftarrow c_6$
$n = 2$______$c_1 \leftarrow c_2 \leftarrow c_3 \leftarrow c_4 \leftarrow c_5 | c_6$
$n = 6$______$c_1 \leftarrow c_2 \leftarrow c_3 | c_4 \leftarrow c_5 | c_6$
$n = 24$_____$c_1 \leftarrow c_2 | c_3 | c_4 \leftarrow c_5 | c_6$
$n = 120$____$c_1 \leftarrow c_2 | c_3 | c_4 | c_5 | c_6$
$n = 720$____$c_1 | c_2 | c_3 | c_4 | c_5 | c_6$

¡Pero pará un poco!
Spoiler: mostrar
Esta conclusión la sacamos de asumir que dos cantantes no pueden querer cantar después de uno solo, lo cual no en todos los casos es cierto. Si esto fuera cierto, entonces claramente no hay manera de acomodar a los $6$ cantantes, y $n = 0$. Como ejemplo, si tenemos que $c_1$ es Miley Cyrus cantando rock, claramente $c_1 \leftarrow c_2$, $c_1 \leftarrow c_3$, $c_1 \leftarrow c_4$, $c_1 \leftarrow c_5$ y $c_1 \leftarrow c_6$, entonces $n = 0$ y Miley Cyrus no puede cantar :cry:
Problema 363
Sea $D$ en el lado $BC$ del triángulo acutángulo $ABC$ de modo que $AD = AC$. Sean $P$ y $Q$ respectivamente los pies de las perpendiculares desde $C$ y $D$ al lado $AB$. Se sabe que $AP^2 + 3 BP^2 = AQ^2 + 3 BQ^2$. Calcular la medida del ángulo $A\widehat{B}C$.
OWEEEEEEE

Responder