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
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:
Hallar todas las funciones $f$ que vayan de los naturales a los naturales tales que:
Suscribirse a:
Comentarios de la entrada (Atom)
3 comentarios:
¿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$.
Perdón, donde dice $...=f^{f(m)(m)=m+1}$ debería decir $...=f^{f(m)}(m)=m+1$
Publicar un comentario