Maratón de Problemas

[juandodyk]

Solucion 381

Spoiler: mostrar

Trivial usando Cauchy-Schwarz. Tenemos
$$\left(\frac{4x}{y+z}+\frac{y}{z+x}+\frac{z}{x+y}\right)(x(y+z) + y(z+x) + z(x+y)) \geqslant (2x + y + z)^2,$$
asi que $4(xy+yz+zx) \geqslant (2x + y + z)^2$, es decir, $2yz \geqslant 4x^2 + y^2 + z^2$, pero $4x^2 + y^2 + z^2 \geqslant 2yz$ con igualdad sii $x=0$ y $y=z$. Luego hay igualdad, y por lo tanto $\dfrac{x+z}{y} = 1$.

Problema 382
Sea $n$ y $k$ enteros positivos tales que $k\geqslant n$ y $k-n$ es par. Se tienen $2n$ lámparas numeradas $1,2,\ldots ,2n$, cada una de las cuales puede estar encendida o apagada. Inicialmente todas las lámparas están apagadas. Se consideran las sucesiones de pasos: en cada paso se selecciona exactamente una lámpara y se cambia su estado (si está apagada se enciende, si está encendida se apaga).
Sea $N$ el número de sucesiones de $k$ pasos al cabo de los cuales las lámparas $1,2,\ldots ,n$ quedan todas encendidas, y las lámparas $n+1,\ldots ,2n$ quedan todas apagadas.
Sea $M$ el número de sucesiones de $k$ pasos al cabo de los cuales las lámparas $1,2,\ldots ,n$ quedan todas encendidas, y las lámparas $n+1,\ldots ,2n$ quedan todas apagadas sin haber sido nunca encendidas.
Calcular la razón $\frac{N}{M}$.

[Emerson Soriano]

Ese problema es de la IMO 2008, P5, justo has publicado su solución.

https://omaforos.com.ar/viewtopic.php?f ... 6c7#p28199

creo que deberías proponer otro problema, uno que no haya sido propuesto en este foro.

[juandodyk]

Uh, bue, no conocia esa regla. No conozco muchos problemas, pero bueno veamos si este te parece OK. No es de ninguna olimpiada.

Problema 382
Dado $n\geq1$ entero definimos la derivada aritmetica $n'$ asi:

• $1'=0$,
• $p'=1$ si $p$ es primo,
• $(ab)'=a'b+ab'$.

Demostrar que si $N\geq1$ entonces
$$\sum_{n=1}^N (n,n') = \sum_{\substack{1\leq n\leq N \\ n \in M}} \left\lfloor\frac{N}{n}\right\rfloor n \prod_{\substack{p^a\mid\mid n \\ p \text{ primo}}} \left( \frac{(p,a)}{p} - \frac{(p,a-1)}{p^2} \right),$$
donde $M$ es el conjunto de los numeros "llenos de cuadrados", i.e., los $n=p_1^{a_1}\ldots p_k^{a_k}$ con $a_1,\ldots,a_k\geq 2$, $(a,b)$ es el minimo comun divisor de $a$ y $b$, y $p^a\mid\mid n$ quiere decir que $p^a$ divide a $n$ pero $p^{a+1}$ no lo divide.

[Gianni De Rico]

Hola, no es tanto una regla en sí, pero la idea de la maratón es proponerle al resto problemas que (idealmente) no conozcan para que puedan pasar un rato pensando y resolviéndolos, subir un problema que ya está en el foro, aunque ya ha pasado (por ejemplo, el Problema 363 de la maratón fue el Problema 2 de Nivel 2 del Nacional 2016), no cumple tanto ese objetivo, por eso en general tratamos de no hacerlo.
Emerson probablemente pensó que estabas más familiarizado con la maratón, pero no creo que lo haya dicho con una mala intención, espero que mi explicación resulte un poco más clara.

[Emerson Soriano]

Uh, bue, no conocia esa regla. No conozco muchos problemas, pero bueno veamos si este te parece OK. No es de ninguna olimpiada.

Problema 382
Dado $n\geq1$ entero definimos la derivada aritmetica $n'$ asi:

• $1'=0$,
• $p'=1$ si $p$ es primo,
• $(ab)'=a'b+ab'$.

Demostrar que si $N\geq1$ entonces
$$\sum_{n=1}^N (n,n') = \sum_{\substack{1\leq n\leq N \\ n \in M}} \left\lfloor\frac{N}{n}\right\rfloor n \prod_{\substack{p^a\mid\mid n \\ p \text{ primo}}} \left( \frac{(p,a)}{p} - \frac{(p,a-1)}{p^2} \right),$$
donde $M$ es el conjunto de los numeros "llenos de cuadrados", i.e., los $n=p_1^{a_1}\ldots p_k^{a_k}$ con $a_1,\ldots,a_k\geq 2$, $(a,b)$ es el minimo comun divisor de $a$ y $b$, y $p^a\mid\mid n$ quiere decir que $p^a$ divide a $n$ pero $p^{a+1}$ no lo divide.

No es tanto si me parece o para yo estar conforme, la idea ya lo dijo Gianni De Rico, se trata de proponer problemas y que, en lo posible, no hayan sido propuestos con anterioridad, ya que no tendría sentido proponer un problema que ya tiene solución en el foro, con esto se trata de enriquecer y dar diversidad al foro con nuevos problemas. Muchas veces es difícil saber si un problema ya fue usado y resuelto en este foro, pero si un usuario nota eso, es bueno que lo mencione. Hace algunos años se planteó que si un problema del maratón no ha sido resuelto en 3 días, el usuario que propuso el problema debe resolverlo y luego proponer el siguiente, de esta manera se mantiene el movimiento en el foro.

[juandodyk]

OK, no me interesa participar en esto si tiene tantas reglas. Hagan como que no postee nada.

[Gianni De Rico]

Bueno, entonces pongo un problema yo

Problema 382
Hallar todos los pares $(a,b)$ de enteros positivos tales que $a\mid b^4+1$, $b\mid a^4+1$ y $\left \lfloor \sqrt{a}\right \rfloor =\left \lfloor \sqrt{b}\right \rfloor$.

Aclaración: $\lfloor x\rfloor$ es el mayor entero menor o igual que $x$, por ejemplo, $\lfloor 1,5\rfloor =1$, $\lfloor 2\rfloor =2$ y $\lfloor \pi \rfloor =3$.

[BrunZo]

Esta es una Maratón de Problemas... creo que la única regla que debería tener es que hay que compartir y disfrutar todos los problemas, sin importar de dónde vengan o cómo sean. No podemos dejar que la burocracia o los prejuicios se entrometan con nuestras ganas de pensar problemas. Por eso, si no les molesta, dejo mis ideas sobre el problema sobre la derivada aritmética

Spoiler: mostrar

Observación 1: Podemos calcular n' como n * (SUMA ai/pi).
Demo:
Primero, demostrémoslo para potencias de primos p^a por inducción en a:
Para a=1, por la definición, p' = 1 = p * (1/p)
Para a>1, al tener p^a = p * p^(a-1) vale que
(p^a)' = p' * p^(a-1) + p * (p^(a-1))'
Por lo que habiendo demostrado que (p^(a-1))' = (a-1) p^(a-2), tenemos
(p^a)' = p^(a-1) + (a-1) p^(a-1) = a p^(a-1)
lo que completa la inducción.
Ahora, vamos a demostrarlo para un entero cualquiera n = PROD pi^ai por inducción en la cantidad de potencias de primos.
Si n = (PROD pi^ai hasta k), entonces
n' = (PROD pi^ai hasta k-1)' * pk^ak + (PROD pi^ai) * (pk^ak)'
Por hipótesis inductiva:
n' = (PROD pi^ai hasta k-1) * (SUMA ai/pi hasta k-1) * pk^ak + (PROD pi^ai hasta k-1) * ak pk^(ak-1)
= (PROD pi^ai hasta k) * (SUMA ai/pi hasta k-1) + (PROD pi^ai hasta k) * ak/pk
= (PROD pi^ai) * (SUMA ai/pi)
= n * (SUMA ai/pi)
lo que completa la inducción.


Llamo f(n) = (n, n').

Observación 2: f es multiplicativa.
Demo:
Escribamos SUMA ai/pi = A/P donde A y P son coprimos.
Entonces f(n) = (n, n') = (n, nA/P) = n/P.
Ahora bien, notemos que si las fracciones ai/pi se escriben como irreducibles, entonces A/P cumple que P es el producto de todos los denominadores irreducibles.
Para reducir una fracción ai/pi, se necesita que pi | ai, en cuyo caso el denominador pasa a ser 1.
Es decir, P es el producto de todos los pi que cumplen que pi /| ai.
Como la propiedad pi | ai solo depende de la potencia de primo en particular, vale que P es multiplicativo.
Como n y P son multiplicativos, es claro que f es multiplicativa, como queríamos.

En particular, f(p^a) = p^a si p | a
= p^(a-1) si p /| a
Y esto es lo mismo que decir que f(p^a) = p^(a-1) * (p,a)


Defino g(n) = SUMA [d * PROD {(p,a)/p - (p,a-1)/p^2} para p^a || d] para d|n, d en M

Observación 3: g es multiplicativa.
Demo:
Supongamos que n = ab con a y b coprimos.
Consideremos entonces:
g(a)g(b) = (SUMA [x * PROD {(p,a)/p - (p,a-1)/p^2} para p^a || x] para x|a, x en M) * (SUMA [y * PROD {(p,a)/p - (p,a-1)/p^2} para p^a || y] para y|b, y en M)
= (SUMA [xy * PROD {(p,a)/p - (p,a-1)/p^2} para p^a || xy] para x|a, y|b, x,y en M)
= (SUMA [d * PROD {(p,a)/p - (p,a-1)/p^2} para p^a || d] para d|n, d en M)
= g(n)
La segunda igualdad se obtiene expandiendo el producto de las sumas, emparjando cada x|a con y|b,
y la tercera igualdad se obtiene al reemplazar d = xy y notando que los (x,y) con x|a, y|b, x,y en M son biyectivos con los d|n, d en M.
Esto demuestra la observación.

En particular,
g(p^a) = SUMA [p^i * {(p,i)/p - (p,i-1)/p^2}] para i = 2,3,...,a.
= SUMA [p^(i-1) (p,i) - p^(i-2) (p,i-1)] para i = 2,3,...,a.
= (p^(a-1) (p,a) - p^(a-2) (p, a-1)) + (p^(a-2) (p,a-1) - p^(a-3) (p, a-2)) + ... + ((p^1 (p,2) - p^0 (p, 1)))
= p^(a-1) (p,a) - p^0 (p, 1)
= p^(a-1) (p,a)


Lema: SUMA [N/n] * t(n) para n=1,...,N = SUMA [SUMA t(d) para d|n] para n=1,...,N.
Demo: Esta igualdad se da ya que en ambas expresiones, t(d) se cuenta una vez por cada múltiplo de d menor o igual a N.

De las observaciones 2 y 3 y los resultados particulares, se ve claramente que f(n) = g(n) = PROD p^(a-1) (p,a) para p^a || n.

Llamemos F(N) = SUMA (n,n') = SUMA f(n)
Llamemos G(N) = SUMA [N/n] * n PROD {(p,a)/p - (p,a-1)/p^2} = SUMA g(n) por el Lema.

Pero como f(n) = g(n) para todo n, queda claro que F(N) = G(N) para todo N, por lo que demostramos el problema.



Siento que esta solución sigue incompleta, je, no logra explicar bien por qué vale la igualdad que vale. ¿Hay alguna mejor intuición sobre la identidad que propusiste @juandodyk? Por ahora sigue parenciéndome loquísimo que valga algo así.

[juandodyk]

@BrunZo dejo comentario sobre el problema:

Spoiler: mostrar

La igualdad es una aplicacion mecanica de inversion de Mobius. Uno puede aplicar esto a cualquier suma $\sum_{n\leq N}f(n)$ con $f$ multiplicativa. La idea es definir $g(n) = \sum_{d\mid n} \mu(n/d) f(n)$, donde $\mu$ es la funcion de Mobius. Luego notar que $f(n) = \sum_{d\mid n} g(d)$. Lo util de esto es que $g(n)$ es multiplicativa (porque $\mu$ y $f$ son multiplicativas) asi que para calcularla basta calcular $g(p^a)$ para $p$ primo. Y ahi notar que $g(p^a) = f(p^a) - f(p^{a-1})$ usando la formula. Asi que obtenemos
$$\sum_{n\leq N} f(n) = \sum_{n\leq N} \sum_{d\mid n} g(d) = \sum_{n\leq N} \left\lfloor \frac{N}{n} \right\rfloor g(n) = \sum_{n\leq N} \left\lfloor \frac{N}{n} \right\rfloor \prod_{p^a\mid\mid n} (f(p^a) - f(p^{a-1})).$$
Es decir, la formula que puse es un caso particular de esta formula, que vale para cualquier $f$ multiplicativa.

En el caso particular de $f(n) = (n,n')$ lo "util" de la formula es que $g(n)=0$ salvo que $n$ sea "lleno de cuadrados" (esto es, que si $p\mid n$ y $p$ es primo, $p^2\mid n$), y hay "muy pocos" numeros llenos de cuadrados, asi que calcular la suma de la derecha es mas facil, porque son "pocos" terminos. (Formalmente, podes ver que la probabilidad de que un numero al azar en $[1,N]$ sea lleno de cuadrados tiende a $0$ cuando $N\to\infty$.)

[Emerson Soriano]

Esta es una Maratón de Problemas... creo que la única regla que debería tener es que hay que compartir y disfrutar todos los problemas, sin importar de dónde vengan o cómo sean. No podemos dejar que la burocracia o los prejuicios se entrometan con nuestras ganas de pensar problemas. Por eso, si no les molesta, dejo mis ideas sobre el problema sobre la derivada aritmética

Spoiler: mostrar

Observación 1: Podemos calcular n' como n * (SUMA ai/pi).
Demo:
Primero, demostrémoslo para potencias de primos p^a por inducción en a:
Para a=1, por la definición, p' = 1 = p * (1/p)
Para a>1, al tener p^a = p * p^(a-1) vale que
(p^a)' = p' * p^(a-1) + p * (p^(a-1))'
Por lo que habiendo demostrado que (p^(a-1))' = (a-1) p^(a-2), tenemos
(p^a)' = p^(a-1) + (a-1) p^(a-1) = a p^(a-1)
lo que completa la inducción.
Ahora, vamos a demostrarlo para un entero cualquiera n = PROD pi^ai por inducción en la cantidad de potencias de primos.
Si n = (PROD pi^ai hasta k), entonces
n' = (PROD pi^ai hasta k-1)' * pk^ak + (PROD pi^ai) * (pk^ak)'
Por hipótesis inductiva:
n' = (PROD pi^ai hasta k-1) * (SUMA ai/pi hasta k-1) * pk^ak + (PROD pi^ai hasta k-1) * ak pk^(ak-1)
= (PROD pi^ai hasta k) * (SUMA ai/pi hasta k-1) + (PROD pi^ai hasta k) * ak/pk
= (PROD pi^ai) * (SUMA ai/pi)
= n * (SUMA ai/pi)
lo que completa la inducción.


Llamo f(n) = (n, n').

Observación 2: f es multiplicativa.
Demo:
Escribamos SUMA ai/pi = A/P donde A y P son coprimos.
Entonces f(n) = (n, n') = (n, nA/P) = n/P.
Ahora bien, notemos que si las fracciones ai/pi se escriben como irreducibles, entonces A/P cumple que P es el producto de todos los denominadores irreducibles.
Para reducir una fracción ai/pi, se necesita que pi | ai, en cuyo caso el denominador pasa a ser 1.
Es decir, P es el producto de todos los pi que cumplen que pi /| ai.
Como la propiedad pi | ai solo depende de la potencia de primo en particular, vale que P es multiplicativo.
Como n y P son multiplicativos, es claro que f es multiplicativa, como queríamos.

En particular, f(p^a) = p^a si p | a
= p^(a-1) si p /| a
Y esto es lo mismo que decir que f(p^a) = p^(a-1) * (p,a)


Defino g(n) = SUMA [d * PROD {(p,a)/p - (p,a-1)/p^2} para p^a || d] para d|n, d en M

Observación 3: g es multiplicativa.
Demo:
Supongamos que n = ab con a y b coprimos.
Consideremos entonces:
g(a)g(b) = (SUMA [x * PROD {(p,a)/p - (p,a-1)/p^2} para p^a || x] para x|a, x en M) * (SUMA [y * PROD {(p,a)/p - (p,a-1)/p^2} para p^a || y] para y|b, y en M)
= (SUMA [xy * PROD {(p,a)/p - (p,a-1)/p^2} para p^a || xy] para x|a, y|b, x,y en M)
= (SUMA [d * PROD {(p,a)/p - (p,a-1)/p^2} para p^a || d] para d|n, d en M)
= g(n)
La segunda igualdad se obtiene expandiendo el producto de las sumas, emparjando cada x|a con y|b,
y la tercera igualdad se obtiene al reemplazar d = xy y notando que los (x,y) con x|a, y|b, x,y en M son biyectivos con los d|n, d en M.
Esto demuestra la observación.

En particular,
g(p^a) = SUMA [p^i * {(p,i)/p - (p,i-1)/p^2}] para i = 2,3,...,a.
= SUMA [p^(i-1) (p,i) - p^(i-2) (p,i-1)] para i = 2,3,...,a.
= (p^(a-1) (p,a) - p^(a-2) (p, a-1)) + (p^(a-2) (p,a-1) - p^(a-3) (p, a-2)) + ... + ((p^1 (p,2) - p^0 (p, 1)))
= p^(a-1) (p,a) - p^0 (p, 1)
= p^(a-1) (p,a)


Lema: SUMA [N/n] * t(n) para n=1,...,N = SUMA [SUMA t(d) para d|n] para n=1,...,N.
Demo: Esta igualdad se da ya que en ambas expresiones, t(d) se cuenta una vez por cada múltiplo de d menor o igual a N.

De las observaciones 2 y 3 y los resultados particulares, se ve claramente que f(n) = g(n) = PROD p^(a-1) (p,a) para p^a || n.

Llamemos F(N) = SUMA (n,n') = SUMA f(n)
Llamemos G(N) = SUMA [N/n] * n PROD {(p,a)/p - (p,a-1)/p^2} = SUMA g(n) por el Lema.

Pero como f(n) = g(n) para todo n, queda claro que F(N) = G(N) para todo N, por lo que demostramos el problema.



Siento que esta solución sigue incompleta, je, no logra explicar bien por qué vale la igualdad que vale. ¿Hay alguna mejor intuición sobre la identidad que propusiste @juandodyk? Por ahora sigue parenciéndome loquísimo que valga algo así.

Esa es la idea fundamental, disfrutar de los problemas. No creo que se trate de burocracia, solo es cuestión de comunicación. Muchas veces he posteado problemas repetidos en la maratón, y otro usuario hizo la observación de que dicho problema ya estaba resuelto en este foro, incluso compartió el link para que los demás usuarios puedan ver el problema con su respectiva solución. Por esa razón, tuve que cambiar el problema por otro, solo es eso, comunicación. Lo mismo le ha pasado a varios usuarios que han compartido problemas repetidos, he visto que otro usuario recalcaba que el problema ya estaba repetido y se posteaba otro. Solo me pareció curioso que alguien se enoje por eso, ya que en todos los años que vengo interactuando en este foro, jamás sucedió que alguien se haga problemas porque le observen que su problema es repetido y que debe cambiarlo.