OFO 2019 Problema 7

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
Mensajes: 217
Registrado: Vie 18 Dic, 2015 12:35 am
Medallas: 8
Nivel: Exolímpico
Ubicación: Córdoba

OFO 2019 Problema 7

Mensaje sin leer por MateoCV » Dom 20 Ene, 2019 12:06 am

Para cada entero positivo $n$ sean $\sigma (n)$ la suma de los divisores positivos de $n$ y $\varphi (n)$ la cantidad de números menores o iguales a $n$ y coprimos con $n$. Por ejemplo $\sigma (6)=1+2+3+6=12$ y $\varphi(6)=2$, al ser $1$ y $5$ los únicos números coprimos con $6$ menores o iguales a $6$.
Demostrar que $$\frac{1}{\sigma (n)}+\frac{1}{\varphi (n)}\geq \frac{2}{n}$$
1  
$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
Mensajes: 217
Registrado: Vie 18 Dic, 2015 12:35 am
Medallas: 8
Nivel: Exolímpico
Ubicación: Córdoba

Re: OFO 2019 Problema 7

Mensaje sin leer por MateoCV » Lun 28 Ene, 2019 1:21 am

Solución oficial:
Spoiler: mostrar
Para $n=1$ el problema es cierto ya que $\sigma(1)=\varphi(1)=1$ y entonces
$\frac{1}{1}+\frac{1}{1}\geq \frac{2}{1}$
Así que a partir de ahora supongamos que $n>1$.
Primero vamos a probar el siguiente lema:
Para todo entero positivo $n$, $\sigma (n) \varphi (n) \leq n^2$
Spoiler: mostrar
Factoricemos a $n$ en primos como $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$ (todos los $p_i$ son distintos).
Luego, es conocido que $\sigma (n)=\frac{p_1^{\alpha_1+1}-1}{p_1-1}\cdots \frac{p_k^{\alpha_k+1}-1}{p_k-1}$ y que $\varphi (n)=p_1^{\alpha_1-1}(p_1-1)\cdots p_k^{\alpha_k-1}(p_k-1)$
Por lo tanto $\sigma (n) \varphi (n)=\frac{p_1^{\alpha_1+1}-1}{p_1-1}p_1^{\alpha_1-1}(p_1-1)\cdots \frac{p_k^{\alpha_k+1}-1}{p_k-1} p_k^{\alpha_k-1}(p_k-1)=
(p_1^{\alpha_1+1}-1)p_1^{\alpha_1-1}\cdots (p_k^{\alpha_k+1}-1)p_k^{\alpha_k-1}\leq p_1^{2\alpha_1}\cdots p_k^{2\alpha_k}=n^2$
Luego por AM-GM y por nuestro lema tenemos que
$\frac{1}{\sigma (n)}+\frac{1}{\varphi (n)}\geq \frac{2}{\sqrt{\sigma(n) \varphi (n)}}\geq\frac{2}{n}$
$2^{82589933}-1$ es primo

Avatar de Usuario
enigma1234

OFO - Medalla de Oro FOFO 8 años - Medalla Especial OFO - Medalla de Plata
Mensajes: 66
Registrado: Sab 03 Jun, 2017 8:07 pm
Medallas: 3
Nivel: 2

Re: OFO 2019 Problema 7

Mensaje sin leer por enigma1234 » Lun 28 Ene, 2019 9:32 am

Spoiler: mostrar
Si $n=1\to\sigma (n)=\varphi(n)=1$ y claramente cumple.
Si $n>1$ y $n=\prod_{i=1}^{m} {{p_i}^{n_i}}$ siendo $p_i$ primos distintos es claro que tendremos que:
$$x=\sigma (n)=\prod_{i=1}^{m}{\frac{{p_i}^{n_i+1}-1}{p_i-1}}$$
$$y=\varphi (n)=\prod_{i=1}^{m}{({p_i}^{n_i}-{p_i}^{n_i-1})}$$
De esto es claro que $y=n+\sum_{d|n,d\neq n}^{}{{x_d}.d}$ donde $x_d=-1,0,1$ entonces es claro que $x+y\geq 2n$ pues $x$ es la suma de divisores.
Ahora:
$$x.y=\prod_{i=1}^{m}{\frac{{p_i}^{n_i+1}-1}{p_i-1}.({p_i}^{n_i}-{p_i}^{n_i-1})}=\prod_{i=1}^{m}{({p_i}^{2.n_i}-{p_i}^{n_i-1})}<\prod_{i=1}^{m} {{p_i}^{2.n_i}}=n^2$$
Entonces $$x.y<n^2,x+y\geq 2n\to \frac{1}{x}+\frac {1}{y}=\frac {x+y}{x.y}>\frac {2}{n}$$
One in a millon...my lucky strike! :D

Avatar de Usuario
Gianni De Rico

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

Re: OFO 2019 Problema 7

Mensaje sin leer por Gianni De Rico » Lun 28 Ene, 2019 11:08 am

Me encantó
Spoiler: mostrar
Para $n=1$ tenemos $\sigma (n)=1=\phi (n)$, por lo que $\frac{1}{\sigma (n)}+\frac{1}{\phi (n)}=\frac{1}{1}+\frac{1}{1}=1+1=2=\frac{2}{1}=\frac{2}{n}$, por lo que el enunciado es verdadero. De ahora en adelante, suponemos $n>1$.
Sea $n=\prod\limits_{i=1}^rp_i^{\alpha _i}$ la factorización en primos de $n$ (con $p_i\neq p_j$ si $i\neq j$ y $\alpha _i\geqslant 1\forall i=1,\ldots ,r$). Luego, es un hecho conocido que $\phi (n)=n\prod\limits_{i=1}^r\frac{p_i-1}{p_i}$ y $\sum\limits_{d\mid n}\phi (d)=n$ (una demostración de esto último puede encontrarse en https://proofwiki.org/wiki/Sum_of_Euler ... r_Divisors).
Veamos que $\sigma (n)=\prod\limits_{i=1}^r(1+p_i+p_i^2+\cdots +p_i^{\alpha _i})=\prod\limits_{i=1}^r\frac{p_i^{\alpha _i+1}-1}{p_i-1}$.
Spoiler: mostrar
La segunda igualdad es verdadera por esta fórmula, veamos por inducción en $r$ que la primera también es cierta.
En efecto, para el caso base $r=1$ tenemos $n=p^{\alpha}$, por lo que los divisores de $n$ son $1,p,p^2,\ldots ,p^{\alpha}$, por lo que la suma de los divisores de $n$ es $1+p+p^2+\cdots +p^{\alpha}=\prod\limits_{i=1}^1(1+p_i+p_i^2+\cdots +p_i^{\alpha})=\prod\limits_{i=1}^r(1+p_i+p_i^2+\cdots +p_i^{\alpha})$. Supongamos como hipótesis inductiva que vale para $r=k$, veamos que vale para $k+1$. En efecto, los divisores de $n'=\prod\limits_{i=1}^{k+1}p_i^{\alpha _i}$ (con $p_{k+1}\neq p_i\forall i=1,\ldots ,k$ y $\alpha _{k+1}\geqslant 1$) son de la forma $d=\prod\limits_{i=1}^{k+1}p_i^{a_i}$ con $0\leqslant a_i\leqslant \alpha _i\forall i=1,\ldots ,k+1$, luego, sacando factor común $p_{k+1}^{a_{k+1}}$ (mientras $a_{k+1}$ recorre todos sus valores posibles) tenemos $\sigma (n')=p_{k+1}^0\sigma (n)+p_{k+1}^1\sigma (n)+\cdots +p_{k+1}^{\alpha _{k+1}}\sigma (n)$ ya que al dividir por $p_{k+1}^{a_{k+1}}$ todos los números de la forma $\prod\limits_{i=1}^{k+1}p_i^{a_i}$ obtenemos todos los números de la forma $\prod\limits_{i=1}^kp_i^{a_i}$, es decir, todos los divisores de $n$. Sacando factor común $\sigma (n)$ tenemos $\sigma (n')=(p_{k+1}^0+p_{k+1}^1+\cdots +p_{k+1}^{\alpha _{k+1}})\sigma (n)$, pero por hipótesis inductiva tenemos $\sigma (n)=\prod\limits_{i=1}^k(1+p_i+p_i^2+\cdots +p_i^{\alpha _i})$, luego $\sigma (n')=(1+p_{k+1}+p_{k+1}^2+\cdots +p_{k+1}^{\alpha _{k+1}})\prod\limits_{i=1}^k(1+p_i+p_i^2+\cdots +p_i^{\alpha _i})=\prod\limits_{i=1}^{k+1}(1+p_i+p_i^2+\cdots +p_i^{\alpha _i})$. La inducción está completa.
Veamos un lema que nos servirá para la demostración.
Lema:
$\sigma (n)+\phi (n)\geqslant 2n$
Demostración:
Spoiler: mostrar
Sea $f(n)=n-\phi (n)$, notemos que $f(n)>0\forall n$ pues $\phi (n)$ es a lo sumo $n-1$ (no puede haber más de $n$ números enteros positivos menores o iguales a $n$, y como $n$ no es coprimo con $n$, no puede haber más de $n-1$ números enteros positivos menores o iguales a $n$ y coprimos con $n$) luego $n>\phi (n)\Rightarrow f(n)=n-\phi (n)>0$, como $\sigma (n)=\sum\limits_{d\mid n}d$, tenemos $\sigma (n)-n=\sum\limits_{d\mid n}d-\sum\limits_{d\mid n}\phi (d)=\sum\limits_{d\mid n}d-\phi (d)=\sum\limits_{d\mid n}f(d)=f(n)+\sum\limits_{d\mid n,d\neq n}f(d)\geqslant f(n)=n-\phi (n)$. Por lo tanto $\sigma (n)-n\geqslant n-\phi (n)\Rightarrow \sigma (n)+\phi (n)\geqslant 2n$.
Ahora, como $\sigma (n),\phi (n)>0$ (pues $\sigma (n)\geqslant 1+n>n>0$ y $\phi (n)\geqslant 1>0$), tenemos $\frac{1}{\sigma (n)}+\frac{1}{\phi (n)}\geqslant \frac{2}{n}\Leftrightarrow \sigma (n)+\phi (n)\geqslant \frac{2}{n}\sigma (n)\phi (n)$.
Veamos que $2n\geqslant \frac{2}{n}\sigma (n)\phi (n)$, esto ocurre si y sólo si $n^2\geqslant \sigma (n)\phi (n)$ (pues $n>0$ por ser un entero positivo).
Tenemos $\sigma (n)=\prod\limits_{i=1}^r\frac{p_i^{\alpha _i+1}-1}{p_i-1}$ y $\phi (n)=n\prod\limits_{i=1}^r\frac{p_i-1}{p_i}$, luego $\sigma (n)\phi (n)=\left (\prod\limits_{i=1}^r\frac{p_i^{\alpha _i+1}-1}{p_i-1}\right )\left (n\prod\limits_{i=1}^r\frac{p_i-1}{p_i}\right )=n\prod\limits_{i=1}^r\frac{p_i^{\alpha _i+1}-1}{p_i}$, por lo tanto $n^2\geqslant \sigma (n)\phi (n)=n\prod\limits_{i=1}^r\frac{p_i^{\alpha _i+1}-1}{p_i}\Leftrightarrow n\prod\limits_{i=1}^rp_i\geqslant \prod\limits_{i=1}^r(p_i^{\alpha _i+1}-1)$.
Como $n=\prod\limits_{i=1}^rp_i^{\alpha _i}$, entonces $n\prod\limits_{i=1}^rp_i=\prod\limits_{i=1}^rp_i^{\alpha _i+1}$, por lo que la desigualdad anterior ocurre si y sólo si $\prod\limits_{i=1}^rp_i^{\alpha _i+1}\geqslant \prod\limits_{i=1}^r(p_i^{\alpha _i+1}-1)$, lo cual es cierto pues $p_i^{\alpha _i+1}\geqslant p_i^{\alpha _i+1}-1>1>0$ ya que los $p_i$ son primos y $\alpha _i+1>\alpha _i\geqslant 1$ para todo $i=1,\ldots ,r$. Luego, $2n\geqslant \frac{2}{n}\sigma (n)\phi (n)$.
Por el Lema tenemos $\sigma (n)+\phi (n)\geqslant 2n\geqslant \frac{2}{n}\sigma (n)\phi (n)$. Por lo tanto $\frac{1}{\sigma (n)}+\frac{1}{\phi (n)}\geqslant \frac{2}{n}$.
[math]

Avatar de Usuario
nico ferres

OFO - Medalla de Plata
Mensajes: 8
Registrado: Mié 23 Abr, 2014 11:24 am
Medallas: 1
Nivel: Exolímpico
Ubicación: Entre Rosario y Capital

Re: OFO 2019 Problema 7

Mensaje sin leer por nico ferres » Lun 28 Ene, 2019 1:09 pm

Spoiler: mostrar
Para comenzar, sea $n = p_1^{\alpha_1} p_2 ^{\alpha_2} \cdots p_k ^ {\alpha_k}$ la descomposición en primos de $n$.

Voy a expresar $\sigma (n)$ y $\varphi (n)$ en función de esta descomposición.

Notemos que sigma es suma de elementos de la forma $p_1^{\beta_1} p_2 ^{\beta_2} \cdots p_k ^ {\beta_k}$ con $0 \leq \beta_i \leq \alpha_i$ para todo $ i = 1,2, \ldots , k$ , pero entonces esta suma se puede escribir como:
$$ (1+p_1+p_1^2+\ldots + p_i^{\alpha_1})(1+p_2+p_2^2+\ldots+ p_2^{\alpha_2}) \cdots (1+p_k+p_k^2+\ldots +p_k^{\alpha_k}) $$.

Ahora usamos la identidad $\frac{x^n-1}{x-1} = x^{n-1}+x^{n-2}+\ldots+1$

Entonces nos queda finalmente que: $\sigma(n) = \frac{p_1^{\alpha_1+1}-1}{p_1-1} \frac{p_2^{\alpha_2+1}-1}{p_2-1} \cdots \frac{p_k^{\alpha_k+1}-1}{p_k-1}$

Para el caso de $\varphi(n)$, es conocido el hecho de que $\varphi(n) = n*(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots(1-\frac{1}{p_k})$

Para resolver el problema usare la desigualdad entre las medias aritmetica y geometrica para dos variables, la misma nos dice que para $a,b \in \mathbb{R}^+$ se cumple que $\frac{x+y}{2} \geq \sqrt{xy}$

En nuestro problema tenemos entonces que:
$$\frac{\frac{1}{\sigma(n)}+\frac{1}{\varphi(n)}}{2} \geq \sqrt{\frac{1}{\sigma(n)\varphi(n)}}$$
Entonces solo quedaria demostrar que: $$\sqrt{\frac{1}{\sigma(n)\varphi(n)}} \geq \frac{1}{n}$$
Pero $$\sqrt{\frac{1}{\sigma(n)\varphi(n)}} = \sqrt{\frac{1}{ \frac{p_1^{\alpha_1+1}-1}{p_1-1} \frac{p_2^{\alpha_2+1}-1}{p_2-1} \cdots \frac{p_k^{\alpha_k+1}-1}{p_k-1} * n * (\frac{p_1-1}{p_1})(\frac{p_2-1}{p_2})\cdots(\frac{p_k-1}{p_k}) }} = \sqrt{\frac{1}{ \frac{p_1^{\alpha_1+1}-1}{p_1} \frac{p_2^{\alpha_2+1}-1}{p_2} \cdots \frac{p_k^{\alpha_k+1}-1}{p_k} * n }}$$

Ahora usamos que $p_i^{\alpha_i+1}-1 \leq p_i^{\alpha_i+1}$, con $ i = 1,2, \ldots , k$, por lo tanto:

$$\sqrt{\frac{1}{ \frac{p_1^{\alpha_1+1}-1}{p_1} \frac{p_2^{\alpha_2+1}-1}{p_2} \cdots \frac{p_k^{\alpha_k+1}-1}{p_k} * n }} \geq \sqrt{\frac{1}{ \frac{p_1^{\alpha_1+1}}{p_1} \frac{p_2^{\alpha_2+1}}{p_2} \cdots \frac{p_k^{\alpha_k+1}}{p_k} * n}} = \sqrt{\frac{1}{ p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k} * n}} = \sqrt{ \frac{1}{n*n}} = \frac{1}{n} $$

Esto demuestra lo pedido.
2  
Legalmente puedo manejar una cosechadora

Responder