Bonjour à tous.
Encore un problème qui n'a pas eu de réponses pour l'instant.
Le problème : existe-t-il des fonction f de N dans N vérifiant f(f(f(n)))=2n+3.
La réponse est oui. On peut en construire assez simplement.
Appelons k la fonction k(n)=2n+3
Soit A l'ensemble des nombres entiers qui n'ont pas d'antécédent par k(n); Tout entier peut s'écrire de façon unique n=k^[e(n)](b(n)) avec b(n) dans A. De l'équation initiale, on tire f(k(n))=k(f(n)) et donc f(k^[p](n)^)=k^[p](f(n)) et donc :
f(n)=k^[e(n)](f(b(n))) pour tout entier n.
Il suffit donc de définir f sur A de façon adéquate pour définir f sur N.
Pour ce faire, séparons si possible A en trois sous-ensembles disjoints équipotents A = A1 U A2 U A3.
(dans notre exemple, cela est possible car A est infini dénombrable : A est l'ensemble des nombres pairs complété par {1} : A = {0, 1, 2, 4, 6, 8, 10, ... }. Ce ne serait pas possible par exemple si A était de cardinal fini non multiple de 3, par exemple si on avait k(n)=n+2)
Soit g une bijection de A1 dans A2 et h une bijection de A2 dans A3.
On peut définir f ainsi :
1) si n est dans A1, f(n)=g(n)
2) si n est dans A2, f(n)=h(n)
3) si n est dans A3, f(n)=k(g^[-1](h^[-1](n)))
4) si n n'est pas dans A, b(n) est dans A et f(n)=k^[e(n)](f(b(n)))
Ceci définit parfaitement une fonction f(n) sur N. Il est [assez] facile de vérifier qu'elle respecte bien l'équation f(f(f(n)))=k(n) :
1) Si n est dans A1 :
f(n)=g(n) et f(n) est dans A2, donc :
f(f(n))=h(f(n))= h(g(n)) et f(f(n)) est dans A3, donc :
f(f(f(n)))=k(g^[-1](h^[-1](f(f(n))))) = k(g^[-1](h^[-1](h(g(n)))))=k(n)
CQFD
2) si n est dans A2 :
f(n)=h(n) et f(n) est dans A3, donc :
f(f(n))=k(g^[-1](h^[-1](f(n))))=k(g^[-1](h^[-1](h(n))))=k(g^[-1](n)) et f(f(n)) n'est pas dans A, donc :
f(f(f(n))) = k^[e(f(f(n)))](f(b(f(f(n)))))
Comme g^[-1](n) est dans A1, et que f(f(n))=k(g^[-1](n)), on a : e(f(f(n)))=1 et b(f(f(n)))=g^[-1](n), et donc :
f(f(f(n)))=k^[1](f(g^[-1](n))).
Comme g^[-1](n) est dans A1, f(g^[-1](n))= g(g^[-1](n)) = n et donc :
f(f(f(n)))=k^[1](f(g^[-1](n))) = k(n)
CQFD
3) si n est dans A3 :
f(n) = k(g^[-1](h^[-1](n))) et f(n) n'est pas dans A, donc :
f(f(n)) = k(f(g^[-1](h^[-1](n)))) = k(h^[-1](n)) car g^[-1](h^[-1](n)) est dans A1. f(f(n)) n'est pas dans A, donc :
f(f(f(n))) = k(f(h^[-1](n))) = k(n) car h^[-1](n) est dans A2
CQFD
4) si n n'est pas dans A :
f(n)=k^[e(n)](f(b(n))) et f(n) n'est pas dans A, donc :
f(f(n))=k^[e(n)](f(f(b(n)))) et f(f(n)) n'est pas dans A, donc :
f(f(f(n))) = k^[e(n)](f(f(f(b(n))))). Mais f(f(f(b(n)))=k(b(n)) puisque b(n) est dans A et que les 3 paragraphes précédents montrent que f(f(f(x))) = k(x) pout tout x dans A. Donc :
f(f(f(n))) = k^[e(n)](k(b(n))) = k(n)
CQFD
Voilà.
Cette mécanique montre qu'il est toujours possible de trouver f telle que f^[p](n)=k(n) dès lors que l'ensemble A des éléments sans antécédents par k est infini ou fini de cardinal divisible par p.
Accueil 