domingo, 12 de enero de 2014

Problema del Día 10-01-14 (Xavi)

Perdonen el retraso
Hallar todas las funciones $f$ que vayan de los naturales a los naturales tales que:

$f^{f(n)}(n)=n+1$

Donde $f^{k}(n)$ es el resultado de aplicar la función $f$ a $n$ $k$ veces

3 comentarios:

Juan dijo...

¿Va así?

Llamo a la ecuación dada en el problema, la ecuación (1). Llamemos $x_0=1$, $x_1=f(1)$, $x_2=f^2(1)$, ..., $x_k=f^k(1)$, etcétera.

Entonces demostraré por inducción que $x_{f(1)+...+f(m-1)}=m$ para todo $m\ge 2$.

El caso base se demuestra con $n=1$ en (1).
El paso inductivo es así:

$x_{f(1)+...+f(m)} = f^{f(m)}(x_{f(1)+...+f(m-1)})=$$f^{f(m)(m)=m+1$

por (1) con $n=m$.

Así, queda demostrada la inducción, y por tanto $x_{f(1)+...+f(m-1)}=m$ para todo $m\ge 2$ y $x_0=1$.

Ahora bien, supongamos que hay dos naturales $a$ y $b$ tales que $f(a)=f(b)$. Entonces

$a+1=f^{f(a)}(a)=f^{f(a)-1}(f(a))=$$f^{f(b)-1}(f(b))=f^{f(b)}(b)=b+1$

y así $a=b$. Por tanto $f$ es inyectiva.

Ahora supongamos que escribo la secuencia $x_0, x_1, ...$ en un pizarrón. En el primer espacio está el $1$, más adelante está el $2$, más adelante el $3$, y así, por la inducción. Así, hay una subsecuencia de $x_0, x_1, ...$ en la cual aparecen todos los naturales en orden. Esta subsecuencia no puede ser la misma$x_0, x_1, ...$, ya que ello implicaría $1=f(1)=f(2)$, que es falso por ser $f$ inyectiva.

Así, hay al menos un natural $k$ que aparece al menos dos veces en la secuencia. Digamos $x_w=x_u=k$ y $w \textless u$. Entonces $f^{u-w}(k) = k$. Ahora, en la secuencia $k, f(k), ..., f^{u-w-1}(k)$ aparecen un número finito (al menos uno) de naturales. Pero es fácil ver que ésto nos garantiza que la secuencia $x_0, x_1, ...$ es periódica desde éste punto, desde $x_w$.

Así, hay un natural $M$ suficientemente grande tal que $N=f(1)+...+f(M-1) \ge w$ y tal que $M$ no aparezca en la secuencia finita $x_w, x_{w+1}, ..., x_{u-1}$. Pero $M=x_N$ y $x_N$ sí aparece en esa secuencia finita.

¡Contradicción!

Así, no existe tal función $f$.

Juan dijo...
Este comentario ha sido eliminado por el autor.
Juan dijo...

Perdón, donde dice $...=f^{f(m)(m)=m+1}$ debería decir $...=f^{f(m)}(m)=m+1$

Publicar un comentario