Bonjour à tous,
Voici le problème que j'ai eu cette après midi en colle de maths, mon prof m'a demandé de le terminer à la maison :
Soit f une application de N dans N, tel que :
f(n+1) = f(f(n))
Montrez que f ne peut être que l'identité de N.
Il m'a conseiller d'abord de prouver que f(0) = 0, mais même cela m'echappe.
Pourriez vous me donner quelques indications ?
Merci
Salut,
J'ai peur qu'il te manque des hypothèses (surjectivité ?) car si je prends f : n->n+1, elle vérifie ta propriété mais n'est pas l'identité.
AHHH pardon, j'ai fait une petite bourbe dans l'enoncé :
Soit f une application de N dans N, tel que :
f(n+1) > f(f(n)) (C'est superieur strict et non egal)
Désolé...
C'est un problème des Olympiades d'il y a qq années, que je trouve très difficile.
On peut facilement montrer que f(n)>0 pour n>0, après ça se complique
J'avoue ne pas trouver. Du coup je suis curieux de voir une solution.Envoyé par ericcc
C'est surtout que si l'indice de ton prof était juste, on aurait f=0AHHH pardon, j'ai fait une petite bourbe dans l'enoncé :
Soit f une application de N dans N, tel que :
f(n+1) > f(f(n)) (C'est superieur strict et non egal)
Désolé...
Le professeur qui m'a coller m'as dit qu'étant donné qu'on peut se douter qu'il va falloir utilisé la récurence dans notre démonstration, on peut aussi tenter de raisonné sur son equivalent : le bon ordre.
Il m'a conseiller montrer que f(0) est le minimum de la fonction.
en effetC'est surtout que si l'indice de ton prof était juste, on aurait f=0, sa m'apprendra !
( En tout cas, sa me rassure qu'il n'y ai pas que moi qui pietine )
Bon, on arrive déjà à montrer que le minimum est atteint en 0 et pas ailleurs.
m=min(f) atteint en N0.
On suppose N0>=1
m=f(N0)=f(N0-1+1)>f(f(N0-1)) qui contredit m minimum de f.
Donc m est atteint en 0.
Après montrer que c'est 0.
EDIT: ah f(0) ne doit pas être égal à 0 ?
Non justement, on doit prouver que f(0) = 0, en fait on doit prouver que f = id
Salut.
Bon je pense avoir une solution mais je ne démontre rien de précis au départ genre f(0) et tout ça.
Cliquez pour afficher
Taar.
J'avoue je galere trop aussi. J'ai montré que :
f(n) > f^(n+1) (0) mais ca je pense que tout le monde l'a.
A mon avis apres ya une histoire de dénombrabilité de N , ou de bijection mais je suis une quiche a ca : ramenez du monde !!
Pour montrer que f(0)=0, continuons le raisonnement de Ledescat : si m supérieur ou égal à 1, on a f(m)=f(m-1+1)>f(f(m-1))
Donc.
Donc
On peut continuer comme ça très longtemps, en construisant une suite strictement décroissante, qui par le principe de desecente infinie de Fermat, doit être constante à partir d'un certain rang. Mais alors ça contredit, justement, cette décroissance stricte que l'on construit...
Donc m=0 : f(0) = 0.
Je détaille mon point 3. (le post de Gwyddon me montre que mon expression "dérouler l'inégalité" est en fait ambiguë) :
Cliquez pour afficher
Taar.
Taar me semble avoir trouvé une voie possible.
Sinon on peut aussi le prendre ainsi :
f(n)>f(f(n-1)) pour n>0 donc f(n) n'est pas minimal. Donc le min de l'image de f est f(0). Ca c'est déjà dit.
Montrons ensuite que f est strictement croissante par récurrence.
On suppose que f(0)<f(1)<...<f(n) et f(k)<f(m) pour tout 0<=k<=n et tout m>n.
{f(m) ; m>n} a un minimum atteint pour m=p.
p=n+1, en effet :
on a f(p)=f(p-1+1)>f(f(p-1)) donc f(p-1)<=n par définition de p.
Or comme f(0)<f(1)<...<f(n) on a f(k)>=k pour tout 0<=k<=n, en particulier n<=f(n).
On aboutit à f(p-1)<=f(n) et donc à p-1<=n par hypothèse de récurrence et finalement à p=n+1.
Comme p=n+1 est la seule valeur possible pour p, f(n+1) est un minimal strict, l'hypothèse de récurrence est vraie au rang n+1.
Et on conclut alors aisément, en effet :
on a déjà f(n)>=n comme pour toute application de N dans N strictement croissante.
Et on a f(n+1)>f(f(n)) donc n+1>f(n).
Finalement f(n)=n
Voilà comment je montre cela : supposons qu'il existe a>0 tel que f(a)=0, alors a-1 existe, et f(f(a-1))<f(a)=0 c'est impossible.
