lunes, 11 de abril de 2011

Problema del día

Les dejo este problema en lugar de la competencia de Invierno, a algunos ya se los había platicado alguna vez pero según yo nadie lo resolvió completo.

Encuentra todas las funciones $f:\mathbb{N} \to \mathbb{N}$ tales que

\[(f(n))^p\equiv n\pmod {f(p)}\]

para cualquier $n\in \mathbb{N}$ y $p$ primo.

¡Échenle ganas a los entrenamientos! ¡Les quedan tres meses antes de la IMO, en los que pueden aprender mucho si los aprovechan!

6 comentarios:

Jorge 'Chuck' dijo...

Me parece que lo acabé:
Primero veamos que $(f(p))^{p}\equiv 0\equiv p(mod f(p))$ por lo que $f(p)|p$ pero como $f:\mathbb{N}\to\mathbb{N}$, entonces $f(p)=1$ ó $f(p)=p$ Siendo $\mathbb{P}$ el conjunto de los números primos, consideremos $S=\{q\in\mathbb{P}| f(q)=q\}$ y llamemos al producto de todos estos (asumiendo que es finito), $M$. Primero, por el Teorema de Fermat, $(f(n))^{p}\equiv f(n)\equiv n(mod q)$, $\forall q\in S$ y por el Teorema Chino del Residuo, $f(n)\equiv n(mod M)$. De donde vemos que para $p\in\mathbb{P}$ pero $p\notin S$, $f(p)\equiv p(mod M)$. De modo que $\forall p\in\mathbb{P}$ tal que $p<M$, entonces $p\in S$. Ahora, por el Teorema de Bertrand, entre el primo más grande de $S$ (suponiendo que no es $2$) y su doble hay al menos otro primo, y como todos los primos menores al más grande están en $S$, $M$ es mayor al doble de ese primo, por lo que hay un primo más grande incluído en $S$. De donde vemos que si $S$ tiene un primo mayor a $2$, entonces tiene una cantidad infinita de términos y entonces es claro que $f(n)=n$ para todo $n\in\mathbb{N}$ ya que no importa qué tan grande hagamos al producto de muchos primos, $f(n)\equiv n(mod M)$ siendo $M$ el producto y entonces como $M$ puede ser tan grande como queramos, $f(n)=n$. Si $S$ es un conjunto vacío, entonces $f(n)=a_{n}$ para algún $a_{n}\in \mathbb{N}$ para todo $n$ no primo, y $f(p)=1$ para todo primo. Si $S$ contiene únicamente al $2$, entonces $f(2n)=2a_{2n}$ y $f(2n+1)=2a_{2n+1}-1$ y $f(p)=1$ excepto para $p=2$.

Jorge 'Chuck' dijo...

por ahí al usar el Teorema de Fermat, escribí $p$ en vez de $q$ y $q$ en vez de $f(q)$

Flavio dijo...

ya lo habia hecho completo, luego lo posteo

IrvinG dijo...

Bien Chuck! Fue ingeniosa la forma en la que aplicas el postulado de Bertrand. Aunque aquí en le blog no importa tanto, si te recomiendo que escribas un poco más ordenado. Es importante cuando vayas a dividir en casos, decir cuales serán éstos desde el inicio para que los que lean la prueba puedan seguirla más fácilmente.

DANIELIMO dijo...

creo que ya me salio

Georges dijo...

Poniendo n=p tenemos que f(p)= 1 o . Si f(p)=1 para todo primo entonces claramente cualquier función cumple.

Ahora sea q un primo tal que f(q)=q entonces f(n)=(f(n))"p=n mod q por lo que q divide a f(n)-n para todo n. Ahora si existe infinitos primos que sean puntos fijos entonces infinitos primos dividen a f(n)-n para toda n por lo tanto f(n)-n=0 para toda n es decir f(n)=n para toda n.

Por lo tanto supongamos que los primos que son puntos fijos son finitos o acabamos entonces a partir de cierto punto todos los primos p cumplen que f(p)=1. Si existe un primo mayor que dos que es punto fijo digamos r, entonces si consideramos la sucesión rs+2 por dirchlet hay infinitos primos, por lo tanto tiene que haber infinitos primos t tales que sea. Parte de la sucesión y que f(t)=1 pero entonces si ponemos en la función original n=t y p=r nos da que 1=2 mod r lo cual es una contradicción.

Ahora si 2 es el único primo punto fijo entonces con que la función cumpla f(n)=n mod 2 funciona. Fin

Publicar un comentario