2018 TST USA

Avatar de Usuario
Emerson Soriano

OFO - Mención OFO - Medalla de Oro OFO - Medalla de Plata OFO - Medalla de Bronce
Mensajes: 786
Registrado: Mié 23 Jul, 2014 10:39 am
Medallas: 4

2018 TST USA

Mensaje sin leer por Emerson Soriano » Lun 16 Abr, 2018 12:23 pm

Para cada entero positivo $n$, se define como $\sigma (n)$ a la suma de todos los divisores positivos de $n$.
Fijamos un entero positivo $n$. Si $a_k$ es el $k-$ésimo entero positivo primo relativo con $n$, demuestre que $a_n\geq \sigma (n)$. ¿En qué casos ocurre la igualdad?
Última edición por Emerson Soriano el Lun 16 Abr, 2018 12:42 pm, editado 1 vez en total.

Avatar de Usuario
Fran5

OFO - Medalla de Oro OFO - Jurado FOFO Pascua 2017 - Jurado
Mensajes: 813
Registrado: Mié 21 Mar, 2012 1:57 pm
Medallas: 5
Nivel: Exolímpico
Ubicación: Santa Fe

Re: 2018 TST USA

Mensaje sin leer por Fran5 » Lun 16 Abr, 2018 12:40 pm

Suponemos que la sucesión $a_k$ depende de $n$, no?
"Al toque Roque // Al pique Quique // Tranca palanca // No pasa nada // Argentina Gana // La tenés adentro // Costa Rica te entro"

Avatar de Usuario
Emerson Soriano

OFO - Mención OFO - Medalla de Oro OFO - Medalla de Plata OFO - Medalla de Bronce
Mensajes: 786
Registrado: Mié 23 Jul, 2014 10:39 am
Medallas: 4

Re: 2018 TST USA

Mensaje sin leer por Emerson Soriano » Lun 16 Abr, 2018 12:41 pm

Sí. Ahora modificó el enunciado para que se entienda mejor.

jujumas

OFO - Mención OFO - Medalla de Plata FOFO 7 años - Medalla Especial OFO - Oro perfecto FOFO Pascua 2017 - Medalla
OFO - Medalla de Oro
Mensajes: 326
Registrado: Dom 26 Oct, 2014 8:30 pm
Medallas: 7
Nivel: 2

Re: 2018 TST USA

Mensaje sin leer por jujumas » Lun 16 Abr, 2018 4:57 pm

Y supuestamente este es el más facil :(
Solución:
Spoiler: mostrar
Lema 1: $\sum_{d \mid n} \phi (d) = n$.
Demostración: Consideremos los enteros positivos del $1$ al $n$. Para cada divisor $d_i$ de $n$, decimos que un entero $k$ pertenece al grupo $D_i$ si $mcd(k;n)=d_i$. Luego, $k$ $D_i$ si y sólo sí al ser $k$ y $n$ divididos por $d_i$, ambos resultados son coprimos. Luego, $|D_i|= \phi (\frac{n}{d_i})$, y sumando en todos los grupos nuestro Lema esta demostrado.

Sean ahora $d_1$, $d_2$, $\dots$ $d_x$ los divisores de $x$, de menor a mayor. Consideremos los siguientes $x$ conjuntos:

- En el conjunto $1$, el número $1$
- En el conjunto $2$, los $d_2$ primeros números que no aparecieron en el conjunto $1$.
- En el conjunto $3$, los $d_3$ primeros números que no aparecieron en los conjtuntos $1$ ni $2$.
$\dots$
- En el conjunto $x$ los $n$ primeros números que no aparecieron en los conjuntos $1$, $2$, $3$, $\dots$, o $x-1$.

Claramente $\sigma (n)$ es el mayor elemento del conjunto $x$.

Ahora, notemos que el problema es equivalente a ver que en estos conjuntos habrá a lo sumo $n$ enteros coprimos con $n$. Para ver esto, notemos que para todo $i$, en el conjunto $d_i$ habrá números con todos los restos entre $1$ y $d_i$ módulo $d_i$, y que todo número coprimo con $n$ será en particular coprimo con $d_i$. Luego, en el conjunto $d_i$ habrá a lo sumo $\phi (d_i)$ enteros coprimos con $n$, lo que por el Lema 1 equivale a la primera parte del problema.

Para la segunda parte, notemos que la igualdad se obtiene si y sólo sí, para todo divisor $d$ de $n$, que $k$ sea coprimo con $d$ implica que $k$ es coprimo con $n$. Notemos que si dos o más primos $p_1$, $p_2$, $\dots$ $p_y$ dividen a $n$, y tomamos $p_1$ como el menor de estos primos, tenemos que $p_1$ es coprimo con $p_2$, menor que $p_2$, y que $p_1$ no es coprimo con $n$. Luego, $n$ solo puede ser una potencia de un primo.

Pero notemos que en este caso, si $n=p^k$, dividiendo en conjuntos como en la primer parte, tenemos que en cada conjunto la cantidad de números coprimos con $p^k$ es exáctamente $\phi (d_i)$ para todo grupo $i$. Luego, por el Lema 1, estamos nuevamente.

Responder