OFO 2020 Problema 11

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
MateoCV

OFO - Medalla de Bronce FOFO 7 años - Medalla Especial OFO - Medalla de Oro FOFO Pascua 2017 - Medalla OFO - Medalla de Plata
FOFO 8 años - Jurado OFO - Jurado FOFO Pascua 2019 - Jurado
Mensajes: 223
Registrado: Vie 18 Dic, 2015 12:35 am
Medallas: 10
Nivel: Exolímpico
Ubicación: Córdoba

OFO 2020 Problema 11

Mensaje sin leer por MateoCV » Mar 21 Ene, 2020 11:57 pm

Determinar el mayor número real $c$ que cumple la siguiente propiedad: para todo entero $n>1$, el promedio de todos los divisores positivos de $n$ es al menos $c \sqrt{n}$.
$2^{82589933}-1$ es primo

Avatar de Usuario
MateoCV

OFO - Medalla de Bronce FOFO 7 años - Medalla Especial OFO - Medalla de Oro FOFO Pascua 2017 - Medalla OFO - Medalla de Plata
FOFO 8 años - Jurado OFO - Jurado FOFO Pascua 2019 - Jurado
Mensajes: 223
Registrado: Vie 18 Dic, 2015 12:35 am
Medallas: 10
Nivel: Exolímpico
Ubicación: Córdoba

Re: OFO 2020 Problema 11

Mensaje sin leer por MateoCV » Sab 01 Feb, 2020 12:22 am

Aquí vamos a publicar la solución oficial.
$2^{82589933}-1$ es primo

Avatar de Usuario
Sandy

OFO - Medalla de Bronce OFO - Medalla de Plata
Mensajes: 90
Registrado: Lun 27 Nov, 2017 1:59 am
Medallas: 2
Nivel: 3

Re: OFO 2020 Problema 11

Mensaje sin leer por Sandy » Sab 01 Feb, 2020 12:55 am

MateoCV escribió:
Mar 21 Ene, 2020 11:57 pm
Determinar el mayor número real $c$ que cumple la siguiente propiedad: para todo entero $n>1$, el promedio de todos los divisores positivos de $n$ es al menos $c \sqrt{n}$.
No, no estoy para nada orgulloso.
Spoiler: mostrar
Lema $1$: $\sum_{i=0}^{t} x^i=\frac{x^{t+1}-1}{x-1}$
Demostración:
Spoiler: mostrar
Sea $Y=\sum_{i=0}^{t} x^i$
$x\times Y=\sum_{i=0}^{t} x^{i+1}=\sum_{i=1}^{t+1} x^{i}=x^{t+1}-1+\sum_{i=0}^{t} x^i= x^{t+1}-1+Y$
$\Rightarrow Y\times (x-1)=x^{t+1}-1\Rightarrow Y=\frac{x^{t+1}-1}{x-1}$
Sea $C(n)$ la cantidad de divisores de $n$.
Sea $S(n)$ la suma de los divisores de $n$.
Sea $P(n)=\frac{S(n)}{C(n)}$ el promedio de los divisores de $n$.
Sea $f(n)=\frac{P(n)}{\sqrt{n}}$.
Lo que buscamos es el mayor $c$ tal que, para todo $n$ entero, $c\leq f(n)$, es decir, el menor valor de $f(n)$ (si es que existe).
Sean $m, k$ dos enteros y $p$ un primo, tales que $v_p(m)=0$. Veremos que $f(m\times p^k)\geq f(m)$, lo que implica que el menor valor de $f(n)$ se da cuando existe un solo primo en su factorización (es decir, $n$ es potencia de un primo), ya que ahí no podemos seguir dividiendo por $p^k$ y que quede un número al cual no divida $p$, ya que quedaría $1$, pero queremos $n>1$.
Buscaremos entonces $f(m\times p^k)$ en función de $f(m), p, k$.
Sabemos que la cantidad de divisores de $m$ es el producto de los siguientes de los exponentes de los primos en su factorización. Dado que $p$ no aparece en la factorización de $m$, $C(m\times p^k)=(k+1)\times C(m)$.
Sabemos que los divisores de $m$ serán también divisores de $m\times p^k$, como así también los divisores de $m$ multiplicados por $p$, por $p^2$, por $p^3$, …, por $p^k$. Por lo tanto, $S(m\times p^k)=S(m)\times (1+p+p^2+…+p^k)=S(m)\times \frac{p^{k+1}-1}{p-1}$.
Luego $P(m\times p^k)=\frac{ S(m)\times \frac{p^{k+1}-1}{p-1}}{(k+1)\times C(m)}=P(m)\times \frac{p^{k+1}-1}{(p-1)(k+1)}$.
Por lo tanto $f(m\times p^k)= \frac{P(m)}{\sqrt{m\times p^k}}\times \frac{p^{k+1}-1}{(p-1)(k+1)}=f(m) \times \frac{p^{k+1}-1}{(p-1)(k+1)\sqrt{p^k}}$
Entonces lo que queremos demostrar es que $\frac{p^{k+1}-1}{(p-1)(k+1)\sqrt{p^k}}\geq 1$
Dividiremos la demostración en $4$ casos:
$k=1$:
Spoiler: mostrar
$p^2-1\geq 2(p-1)\sqrt{p}$
Pero $p^2-1=(p+1)(p-1)$
$\Rightarrow p+1\geq 2\sqrt{p}$
$p-2\sqrt{p}+1\geq 0$
$(\sqrt{p}-1)^2\geq 0$
$QED$
$p=k=2$:
Spoiler: mostrar
$\frac{2^{2+1}-1}{(2-1)(2+1)\sqrt{2^2}}=\frac{7}{6}\geq 1$
$QED$
$p=2$ y $k\geq 3$:
Spoiler: mostrar
$\frac{2^{k+1}-1}{(2-1)(k+1)\sqrt{2^k}}\geq 1$
$2^{k+1}-1\geq \sqrt{2^k} (k+1)$
$(\sqrt{2^{k+1}}+1) (\sqrt{2^{k+1}}-1)\geq \sqrt{2^k} (k+1)$
Veremos que $\sqrt{2^{k+1}}-1\geq \sqrt{2^k}$ y que $\sqrt{2^{k+1}}+1\geq k+1$
Primero veremos la primera de las dos desigualdades, y elevando ambos lados al cuadrado queda:
$2^{k+1}-2\sqrt{2^{k+1}}+1\geq 2^k$
$2^k\geq 2^{\frac{k+3}{2}}-1$
Pero, para todo $k\geq 3$, vale que $k\geq \frac{k+3}{2}$, luego $2^k\geq 2^{\frac{k+3}{2}}\geq 2^{\frac{k+3}{2}}-1$.
Ahora veamos la segunda desigualdad:
$\sqrt{2^{k+1}}+1\geq k+1$
La derivada del miembro izquierdo es $ln(2)\times 2^{\frac{k-1}{2}}=ln(2^{(2^{\frac{k-1}{2}})})$, y para cualquier $k\geq 3$, queda algo mayor o igual que $ln(2^{(2^{\frac{2}{2}})})=ln(4)$. La derivada del miembro derecho es $1$.
Pero como $4>e$, $ln(4)>1$, por lo tanto, para todo $k\geq 3$, el lado izquierdo crece más rápido que el derecho a medida que crece $k$. Y como para $k=3$ el lado izquierdo ($5$) es mayor que el derecho ($4$), será mayor para todo $k\geq 3$.
Por lo tanto, tenemos que $2^{k+1}-1\geq \sqrt{2^k} (k+1)$
$QED$
$k\geq 2$ y $p\geq 3$:
Spoiler: mostrar
$\frac{p^{k+1}-1}{p-1}\geq (k+1)\sqrt{p^k}$
$\sum_{i=0}^{k} p^i\geq (k+1)\sqrt{p^k}$
El lado izquierdo es claramente mayor que $p^k$, luego con probar que $p^k\geq (k+1)\sqrt{p^k}$ estamos.
$\sqrt{p^k}\geq k+1$
Además, sabemos que $p\geq 3\Rightarrow \sqrt{p^k}\geq \sqrt{3^k}$.
Entonces mostraremos que, para todo $k\geq 2$, $\sqrt{3^k}\geq k+1$
Derivando el miembro izquierdo nos queda $ln(3)\times \frac{3^{\frac{k}{2}}}{2}$.
Pero $3>e$, por lo que, para todo $k\geq 2$ nos queda que la derivada es mayor que $ln(e)\times \frac{3^{\frac{2}{2}}}{2}=\frac{3}{2}>1$.
Y como la derivada del miembro de la izquierda es $1$, tenemos de nuevo que, para todo $k\geq 2$, el miembro izquierdo crece más rápido que el derecho, y como sabemos que para $k=2$ nos queda el miembro izquierdo ($3$) mayor o igual que el miembro derecho ($3$), sabemos que esta desigualdad se mantendrá para todo $k\geq 2$.
Luego $k+1\leq \sqrt{3^k}\leq \sqrt{p^k}\Rightarrow (k+1)\sqrt{p^k}\leq p^k\leq \sum_{i=0}^{k} p^i =\frac{p^{k+1}-1}{p-1}$
$QED$
Entonces ya tenemos mostrado que $f(m\times p^k)\geq f(m)$.
Ahora veremos que $f(p^k)\geq f(p^{k-1})$, y nos quedaremos con que, de existir un mínimo valor para $f$, éste deberá ser la imagen de un número de la forma $p^1$ (es decir, primo).
Los divisores de $p^k$ son $p^0$, $p^1$, $…$, $p^k$, luego $C(p^k)=k+1$ y $S(p^k)=\sum_{i=0}^{k} p^i$.
Luego $P(p^k)=\frac{\sum_{i=0}^{k} p^i}{k+1}$ y entonces $f(p^k)=\frac{\sum_{i=0}^{k} p^i}{(k+1)\sqrt{p^k}}$.
Veamos primero el caso $p=2$:
Notemos primero que $\sum_{i=0}^{k} 2^i=2^{k+1}-1$
En este caso, veremos que $f(2)\leq f(2^k)$ para todo $k\geq 2$.
Veamos que para $k\in \{2, 3, 4, 5\}$ funciona. Tenemos que $f(2)=\frac{3\sqrt{2}}{4}\Rightarrow f(2)^2=\frac{18}{16}$
Spoiler: mostrar
$f(2^2)=\frac{2^{3}-1}{3\times 2}=\frac{7}{6}\Rightarrow f(2^2)^2=\frac{49}{36}>\frac{18}{16}=f(2)^2$
$f(2^3)=\frac{2^{4}-1}{4\times 2\sqrt{2}}=\frac{15\sqrt{2}}{16}\Rightarrow f(2^3)^2=\frac{450}{256}>\frac{18}{16}=f(2)^2$
$f(2^4)=\frac{2^{5}-1}{5\times 4}=\frac{31}{20}\Rightarrow f(2^4)^2=\frac{961}{400}>\frac{18}{16}=f(2)^2$
$f(2^5)=\frac{2^{6}-1}{6\times 4\sqrt{2}}=\frac{63\sqrt{2}}{48}\Rightarrow f(2^5)^2=\frac{7938}{2304}>\frac{18}{16}=f(2)^2$
Ahora veamos los casos donde $k\geq 6$.
Queremos ver que $\frac{3\sqrt{2}}{4}\leq \frac{2^{k+1}-1}{(k+1)\sqrt{2^k}}$
Sabemos que $2^k\leq 2^{k+1}-1$, entonces podemos reducirlo a mostrar que $\frac{(k+1)3\sqrt{2}}{4}\leq \frac{2^k}{\sqrt{2^k}}=\sqrt{2^k}$.
La derivada del lado derecho es $ln(2)\times 2^{\frac{k}{2}-1}$, lo cual es una función creciente (para los reales positivos al menos). Además, con $k=6$ tenemos que es igual a $ln(2)\times 4=ln(16)>ln(3^2)>ln(e^2)=2$. Pero $2^2=4>18/16=(\frac{3\sqrt{2}}{4})^2$, que es el cuadrado de la derivada del lado izquierdo, luego, a partir de al menos $k=6$, el lado derecho crece más rápido que el izquierdo, y en $k=6$, el lado izquierdo ($\frac{21\sqrt{2}}{4}$) es menor que el derecho ($8$), ya que elevando ambos lados al cuadrado queda $64>\frac{441}{8}$.
Por lo tanto ya cubrimos el caso $p=2$.
Veamos ahora qué pasa cuando $p\geq 3$
Veamos ahora que $f(p^k)\geq f(p^{k-1})$, para $k\geq 2$.
Notemos primero que $f(p^k)=\frac{\sum_{i=0}^{k} p^i}{(k+1)\sqrt{p^k}}=\frac{\frac{p^{k+1}-1}{p-1}}{(k+1)\sqrt{p^k}}=\frac{p^{k+1}-1}{(p-1)(k+1)\sqrt{p^k}}$
Por lo tanto queremos demostrar que, para $k\geq 2$, $\frac{p^{k+1}-1}{(p-1)(k+1)\sqrt{p^k}}\geq \frac{p^{k}-1}{(p-1)k\sqrt{p^{k-1}}}$
Cancelando el $\frac{1}{p-1}$ y pasando el denominador de la izquierda multiplicando, y el numerador de la derecha dividiendo, queda:
$\frac{p^{k+1}-1}{p^{k}-1}\geq \sqrt{p}\times \frac{k+1}{k}$
Notemos que $p^{k+1}-1=p^{k+1}-p^{k}+p^{k}-1$, luego la desigualdad se transforma en lo siguiente:
$\frac{p^{k+1}}{p^{k}-1}-\frac{p^{k}}{p^{k}-1}+1\geq \sqrt{p}\times \frac{k+1}{k}$
Además, $\frac{1}{p^{k}-1}>\frac{1}{p^k}$, luego será suficiente demostrar lo siguiente:
$\frac{p^{k+1}}{p^{k}}-\frac{p^{k}}{p^{k}}+1\geq \sqrt{p}\times \frac{k+1}{k}$
$p-1+1\geq \sqrt{p}\times (1+\frac{1}{k})\iff \sqrt{p}\geq 1+\frac{1}{k}$
Pero $k\geq 2\Rightarrow \frac{1}{k}\leq \frac{1}{2}\Rightarrow 1+\frac{1}{k}\leq \frac{3}{2}$
Luego alcanza con demostrar que $\sqrt{p}\geq \frac{3}{2}\iff p\geq\frac{9}{4}$, lo cual es cierto ya que $p\geq 3$.
Por lo tanto, quedó demostrado que, de existir un valor mínimo para $f(n)$, este se dará cuando $n$ es primo.
Sabemos que los únicos divisores de un número primo $p$ son $p$ y $1$, luego $f(p)=\frac{p+1}{2\sqrt{p}}$. Veremos que esta función es creciente, lo cual probará que $p=2$ devuelve el valor de $c$ que buscamos.
Para esto, queremos ver que la derivada nos dé una función mayor a $0$ para todo $p\geq 2$, por lo tanto $\frac{p-1}{4\times p^{\frac{3}{2}}}>0\Rightarrow p-1>0\Rightarrow p>1$, lo cual es cierto, por lo tanto tenemos que $f(n)$ alcanza su menor valor cuando $n=2$. En ese caso, es igual a $\frac{3}{2\sqrt{2}}=\frac{3\sqrt{2}}{4}$, que es el mayor $c$ tal que, para todo $n>1$, el promedio de sus divisores es al menos $c\sqrt{n}$.
Última edición por Sandy el Sab 01 Feb, 2020 1:03 am, editado 3 veces en total.

Avatar de Usuario
NPCPepe

FOFO 9 años - Mención Especial OFO - Medalla de Plata
Mensajes: 33
Registrado: Lun 17 Jun, 2019 9:22 pm
Medallas: 2
Nivel: 2
Ubicación: Argentina

Re: OFO 2020 Problema 11

Mensaje sin leer por NPCPepe » Sab 01 Feb, 2020 12:58 am

Spoiler: mostrar
Para demostrar que $c$ es el mayor número que cumple con estas condiciones, hay que demostrar que para $n>1$, no hay un número $c$ (es decir el promedio de los divisores dividido la raíz de $n$) que sea menor al $c$ que se busca que en este caso va a ser $(1+2)/(\sqrt{2})$, cuando escriba $c$, no va a ser el que pide el enunciado sino el promedio de los divisores dividido la raíz de $n$

Primero sabemos que si $n$ tiene una cantidad par de divisores (es decir no es un cuadrado perfecto), siendo q la cantidad de divisores de $n$ $\sqrt{n}=(d_1*d_2*...*d_q)^{1/q}$, esto gracias a que $n=d_1*d_q=d_2*d_{q-1}=...$ y entonces $\sqrt{n}=((n^{q/2})^{2/q})^{0,5}$ que es lo mismo que la primera ecuación. Los divisores están ordenados de menor a mayor.

$c=((d_1+d_2+...+d_q)/(q(d_1+d_2+...+d_q)^{1/q}))$
por AM-GM, $c>=min(\frac{d_1+d_2+...+d_{q/2}}{q/2}+\frac{d_{q/2+1}+...+d_q}{q/2})/(2*\sqrt{\frac{d_1+d_2+...+d_{q/2}}{q/2}*\frac{d_{q/2+1}+...+d_q}{q/2}})$
el objetivo es comprobar que la mayor mitad de los divisores es mayor o igual al doble de la menor mitad, entonces el mínimo $c$ sería el caso $n=2$, ya que los demas $c$ serían mayores o iguales, para demostrar que $c$ es proporcional a $x/y$ siendo $x$ el mayor divisor, e $y$ el menor, entonces, $x/y=g$:
$c=(x+gx)/(2*\sqrt{gx^2})=(g+1)x/(2x*\sqrt{g})=(g+1)/(2*\sqrt{g})$ entonces $c$ es proporcional a $x/y$ para $x/y>=2$

ahora voy a demostrar que la mayor mitad de los divisores es mayor o igual al doble de la menor mitad:
Los divisores múltiplos de $p$, siendo $p$ un número primo, son la mayoría o la mitad de los divisores, esto se puede demostrar viendo que los divisores multiplos de p, son iguales a los divisores que no son múltiplos de $p$, multiplicados por $p$, al menos una o mas veces. los numeros $a$ son los divisores múltiplos de $p$.
Esta demostración sirve para cuadrados perfectos, pero suponiendo que el divisor $\sqrt{n}$ se repite 2 veces.

Entonces $p(d_1+d_2+...+d_{q/2})<=p(a_1/p+a_2/p+...+a_{q/2}/p)=a_1+a_2+...+a_{q/2}<=d_{q/2+1}+...+d_q$
$p$ es mayor o igual a $2$ entonces el mínimo c es: $(2+1)/(2*\sqrt{2})=(3/(2\sqrt{2}))$ y por ejemplo se puede obtener cuando $n=2$ donde $(1+2)/((1*2)^{0,5})$ da este mismo número

en el caso de que n fuera cuadrado perfecto, debemos quitar un divisor $\sqrt{n}$ de las dos medias para calcular $c$, pero esto no tendría ninguna implicación sobre el mínimo valor de $c$ ya que al quitar $\sqrt{n}$ de la lista de divisores, la relacion entre la mayor y la menor mitad de los divisores aumenta o se mantiene igual, aumentando o manteniendo igual al valor de $c$.

Ahora que encontramos el menor número $c$ que se puede obtener con $n>1$, este mismo va a ser el que pide el problema, porque al aumentarlo más ya no va a poder cumplir las condiciones
$3=569936821221962380720^3+(-569936821113563493509)^3+(-472715493453327032)^3$: esta es la tercer menor solucion descubierta para la ecuación $a^3+b^3+c^3=3$ , las otras dos son $1^3+1^3+1^3=3$ y $4^3+4^3+(-5)^3=3$

Avatar de Usuario
Turko Arias

Colaborador OFO - Medalla de Plata OFO - Medalla de Oro FOFO Pascua 2019 - Medalla OFO - Jurado
Mensajes: 345
Registrado: Lun 28 Nov, 2011 11:39 am
Medallas: 5
Nivel: Ñandú
Ubicación: La Plata, Provincia de Buenos Aires

Re: OFO 2020 Problema 11

Mensaje sin leer por Turko Arias » Sab 01 Feb, 2020 1:03 am

Cortita y al pie (?
Spoiler: mostrar
Lema 1:
$\frac{\sigma (pn)}{\tau(pn) \sqrt{pn}} > \frac{\sigma (n)}{\tau(n)\sqrt n}$. Para todo $n, p$, con $p$ primo.
Spoiler: mostrar
Sea $\alpha=v_p (n)$. Tenemos entonces:
$$\begin{aligned} \frac{\sigma (pn)}{\tau(pn) \sqrt{pn}} & = \frac{\sigma \left( p^{\alpha+1} \right) \sigma \left( \frac{n}{p^{\alpha}} \right)}{ \tau \left( p^{\alpha+1} \right) \tau \left( \frac{n}{p^{\alpha}} \right)\sqrt{pn} }, \\
& = \frac{\left( p^{\alpha+2}-1 \right) \sigma \left( \frac{n}{p^{\alpha}} \right)}{(p-1)(\alpha+2) \tau \left( \frac{n}{p^{\alpha}} \right) \sqrt{pn}}. \end{aligned}$$
Por otro lado y operando de manera análoga llegamos a que:
$$\frac{\sigma(n)}{\tau(n)\sqrt n} = \frac{\left( p^{\alpha+1}-1 \right) \sigma \left( \frac{n}{p^{\alpha}} \right)}{(p-1)(\alpha+1) \tau \left( \frac{n}{p^{\alpha}} \right)\sqrt n}.$$
Simplificando, queremos probar:
$$\begin{array}{c} \dfrac{p^{\alpha+2}-1}{(\alpha+2)\sqrt p} > \dfrac{p^{\alpha+1}-1 }{\alpha+1}, \\
p^{\alpha+1} \left( p\alpha+p-\alpha\sqrt p - 2\sqrt p \right)+ (\alpha+2)\sqrt p - \alpha -1>0, \end{array}$$
Que es cierto para todo $\alpha \geq 0$ y todo $p$ primo.
Lema 2:
$\frac{\sigma(p_1)}{\tau (p_1)\sqrt{p_1} }> \frac{\sigma(p_2)}{\tau(p_2)\sqrt{p_2}}$ para todo par de primos $p_1, p_2$ con $p_1>p_2$.
Spoiler: mostrar
Lo que queremos probar es equivalente a probar $\frac{p_1+1}{\sqrt{p_1}}>\frac{p_2+1}{\sqrt{p_2}}$, que es lo mismo que probar $\left( \sqrt{p_1}-\sqrt{p_2} \right)\left( \sqrt{p_1p_2}-1 \right)>0$, que claramente es cierto.
Del Lema 1 concluímos que con mirar en los números primos nos alcanza, del Lema 2 concluímos que hace falta mirar en el menor de los números primos. Luego, la respuesta es $c=\frac{\sigma(2)}{\tau(2)\sqrt 2}= \frac{3\sqrt 2}{4}$
1  

Avatar de Usuario
Tomás Morcos Porras

OFO - Mención
Mensajes: 26
Registrado: Dom 13 Oct, 2019 5:04 pm
Medallas: 1
Nivel: 2
Ubicación: Córdoba, Córdoba

Re: OFO 2020 Problema 11

Mensaje sin leer por Tomás Morcos Porras » Sab 01 Feb, 2020 2:37 am

Es un poco simple y obvié algunos detalles que tenía anotados, pero es una solución.
Spoiler: mostrar
Defino $s(x)$ como la suma de todos los divisores postivos de $x$, $d(x)$ como la cantidad de divisores positivos de $x$, $p(x)=\frac{s(x)}{d(x)}$, y $r(x)=\frac{p(x)}{\sqrt x}$.
El enunciado del problema pide el mayor real $c$ tal que $r(n)\geq c$ para todo $n$ entero mayor que $1$, o, lo que es lo mismo, el menor valor de $r(n)$ posible, que será el valor que tenga $c$.
Sea $x$ un entero mayor que $1$ y $p$ un primo no divisor de $x$. Se ve fácil que:
$s(xp)=s(x)\times (p+1)$
$d(xp)=d(x)\times 2$
$\sqrt {xp}=\sqrt x\times \sqrt p$
Entonces, podemos afirmar que:
$\frac{r(xp)}{r(x)}=\frac{p+1}{2\times \sqrt p}$
Es decir, que, dado cualquier entero $x$ mayor que $1$, multiplicarlo por un primo $p$ que no lo divida hace que la relación entre el promedio y la raíz aumente drásticamente.
Sea ahora $p$ un primo divisor de $x$. Esto es difícil de formalizar, pero la idea es que multiplicar un número por uno de sus divisores primos hace que la raíz aumente tanto como $\sqrt p$ y el promedio necesariamente mucho más.
Sea entonces $x=p^a\times q^b\times ...\times t^e$, al aumentar $a$ a $a+1$, pasa:
$s(xp)=s(x)+p^{a+1}\times (q^b+q^{b-1}+...+q^0)\times ...\times (t^e+t^{e-1}+...+t^0)$
$d(xp)=d(x)+(b+1)\times ...\times (e+1)$
El crecimiento de $s(x)$ a $s(xp)$ se da a partir de los exponentes fijos en los factores primos de $x$ como limitadores de los grados de polinomios, mientras que el crecimiento de $d(x)$ a $d(xp)$ se da con los exponentes como factores, por lo que esta última escala mucho más lentamente.
Así se demuestra que, para cualesquiera dos números $x$, $y$ tales que $x\mid y$, $r(x)<r(y)$, lo que indica que el número con el menor $r(n)$ tiene que ser primo.
Por último, demuestro que el $2$ es el primo con menor $r(n)$:
Sea $q$ un primo mayor que $2$. Sabemos que:
$s(q)=q+1$
$d(q)=2$
$p(q)=\frac{q+1}{2}$
$r(q)=\frac{q+1}{2\times \sqrt q}$
Al subir el valor de $q$, necesariamente la relación entre el promedio y la raíz va subiendo.
Así, $2$ es el número con menor $r(n)$, que es $\frac{3}{2\times \sqrt 2}$, por lo que $c=\frac{3}{2\times \sqrt 2}$.
Puede que no me reconozcas, pero a lo mejor te suene la cara de un joven que creyó encontrar un ciclo hamiltoniano en el grafo de Petersen, y no satisfecho con creerlo corroborado, subió a un escenario a intentar demostrarlo. Ese soy yo 8-)

Fedex

OFO - Medalla de Plata
Mensajes: 4
Registrado: Mar 31 Dic, 2019 2:26 am
Medallas: 1
Nivel: 3

Re: OFO 2020 Problema 11

Mensaje sin leer por Fedex » Sab 01 Feb, 2020 3:08 am

Última edición por Fedex el Mié 12 Feb, 2020 5:45 pm, editado 1 vez en total.
$B_{ruh}$ $M_{oment}$

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial OFO - Medalla de Oro OFO - Jurado
Mensajes: 1159
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 3
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: OFO 2020 Problema 11

Mensaje sin leer por Gianni De Rico » Sab 01 Feb, 2020 2:56 pm

Sandy escribió:
Sab 01 Feb, 2020 12:55 am
Spoiler: mostrar
Entonces lo que queremos demostrar es que $\frac{p^{k+1}-1}{(p-1)(k+1)\sqrt{p^k}}\geq 1$
Spoiler: mostrar
$$\frac{p^{k+1}-1}{(p-1)(k+1)\sqrt{p^k}}\geq 1\iff \frac{p^{k+1}-1}{(p-1)(k+1)}\geq \sqrt{p^k}$$por el lema$$\frac{p^{k+1}-1}{p-1}=\sum \limits _{i=0}^kp^i$$de donde$$\frac{p^{k+1}-1}{(p-1)(k+1)}=\dfrac{\sum \limits _{i=0}^kp^i}{k+1}$$por AM-GM$$\dfrac{\sum \limits _{i=0}^kp^i}{k+1}\geq \sqrt[k+1]{\prod \limits _{i=0}^kp^i}=\sqrt[k+1]{p^{\frac{k(k+1)}{2}}}=\sqrt{p^k}$$
1  
Queda Elegantemente Demostrado

ktc123

OFO - Medalla de Plata OFO - Medalla de Bronce OFO - Mención
Mensajes: 204
Registrado: Jue 21 Jun, 2012 9:09 pm
Medallas: 5
Nivel: Exolímpico
Ubicación: La Plata, Buenos Aires

Re: OFO 2020 Problema 11

Mensaje sin leer por ktc123 » Sab 01 Feb, 2020 9:23 pm

Peligro, esta solución puede ser danina para su salud
Spoiler: mostrar
Consideremos la factorización en primos de $n$, $n=\prod_k p_k^{\alpha_k}$. Es conocido que la suma de los divisores de $n$ es $S(n)=\prod_k \frac{p_k^{\alpha_k}-1}{p_k-1}$ y que la cantidad de divisores de $n$ es $C(n)=\prod_k (1+\alpha_k)$. Luego, el enunciado es equivalente a hallar el máximo $c$ tal que $$\frac{S(n)}{C(n)}\geq c\sqrt {n} \Leftrightarrow \frac{S(n)}{\sqrt{n}C(n)}=\prod_k \underbrace{\frac{1}{1+\alpha_k}\frac{1}{p_k^{\alpha_k/2}}\frac{p_k^{\alpha_k+1}-1}{p_k-1}}_{\equiv f(\alpha_k,p_k)}\geq c.$$ Ahora nos concentraremos en la función $f$, dejando de lado por un momento al subíndice $k$. Notemos que $f(\alpha=0,p)=1$. A continuación demostraremos que $f(\beta,p)>f(\alpha,p)$ si $\beta>\alpha$. Para eso, reescribimos $f$ como $$f(\alpha,p)=\frac{1}{1+\alpha}\frac{p^{\frac{\alpha+1}{2}}}{p^{\alpha/2}}\frac{p^{\frac{\alpha+1}{2}}-p^{-\frac{\alpha+1}{2}}}{p-1}=\frac{\sqrt{p}}{p-1}\frac{e^{ln(p)\frac{\alpha+1}{2}}-e^{-ln(p)\frac{\alpha+1}{2}}}{1+\alpha},$$ con lo cual $f(\alpha,p)=\frac{2\sqrt{p}}{p-1}\frac{\sinh(ln(p)\frac{\alpha+1}{2})}{\alpha+1}$. A menos de factores multiplicativos, $f$ representa a la función $sinhc(\cdot)$ que es una función creciente. De todos modos, vamos a demostrarlo calculando la derivada de $f$ respecto de $\alpha$.$$\frac{df}{d\alpha}=\frac{d}{d\alpha}\frac{2\sqrt{p}}{p-1}\frac{\sinh(ln(p)\frac{\alpha+1}{2})}{\alpha+1}=\frac{2\sqrt{p}}{p-1}\frac{\cosh(u)}{(1+\alpha)^2}\left(u-\text{tgh}\left(u\right) \right),$$ siendo $u=ln(p)\frac{\alpha+1}{2}$. Y como $\cosh(x)>0$ y $\text{tgh}(x)<x$ si $x>0$ (resultado que sale por ser una función con derivada segunda negativa en dicho dominio), concluimos que $\frac{df}{d\alpha}>0$ si $\alpha>0$. Es decir, que la función $f$ es creciente en $\alpha$ para un primo arbitrario $p$, luego, $f(\alpha,p)\geq 1$. Este último resultado es clave y nos permite concluir que la cota para $c$ es mínima cuando lo exponentes son lo más pequeños posibles. El caso extremo ocurre cuando todos son cero, pero como por enunciado $n>1$, la cota más pequeña se da cuando existe un solo $\alpha$ no nulo, en particular, siendo $\alpha=1$. En tal caso $$\frac{S(p)}{\sqrt{p}C(p)}\stackrel{\alpha=1}{=}\frac{1}{2}\frac{p^2-1}{\sqrt{p}(p-1)}=\frac{p+1}{2\sqrt{p}}=\frac{e^{ln(p)/2}+e^{-ln(p)/2}}{2}=\cosh\left(\frac{ln(p)}{2}\right).$$ Por otro lado, como tanto $cosh(\cdot)$ para argumentos positivos y $ln(\cdot)$ son funciones crecientes, la cota alcanza un mínimo cuando $p=2$. Es decir, que la mínima cota es $\frac{3}{2\sqrt{2}}$, con lo cual $c=\frac{3}{2\sqrt{2}}$.$\square$
7  
¨Todos somos muy ignorantes. Lo que ocurre es que no todos ignoramos las mismas cosas¨

Responder