Maratón de Problemas

[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]

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$.

[Turko Arias]

No quiero arruinar la emoción
Pero técnicamente es a lo sumo el Problema 359, porque:

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

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}$

[Emerson Soriano]

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]

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!

[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?

[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]

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$.

[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.

[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

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$.