Répondre à la discussion
Affichage des résultats 1 à 16 sur 16

Problème d'arithmetique



  1. #1
    Deeprod

    Problème d'arithmetique


    ------

    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

    -----

  2. Publicité
  3. #2
    GuYem

    Re : Problème d'arithmetique

    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é.
    Bravo jolie Ln, tu as trouvé : l'armée de l'air c'est là où on peut te tenir par la main.

  4. #3
    Deeprod

    Re : Problème d'arithmetique

    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é...

  5. #4
    ericcc

    Re : Problème d'arithmetique

    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

  6. A voir en vidéo sur Futura
  7. #5
    GuYem

    Re : Problème d'arithmetique

    Citation Envoyé par ericcc Voir le message
    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.
    Bravo jolie Ln, tu as trouvé : l'armée de l'air c'est là où on peut te tenir par la main.

  8. #6
    Gwyddon

    Re : Problème d'arithmetique

    Citation Envoyé par Deeprod Voir le message
    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 surtout que si l'indice de ton prof était juste, on aurait f=0
    A quitté FuturaSciences. Merci de ne PAS me contacter par MP.

  9. Publicité
  10. #7
    Deeprod

    Re : Problème d'arithmetique

    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.

  11. #8
    Deeprod

    Re : Problème d'arithmetique

    Citation Envoyé par Gwyddon Voir le message
    C'est surtout que si l'indice de ton prof était juste, on aurait f=0
    en effet , sa m'apprendra !

    ( En tout cas, sa me rassure qu'il n'y ai pas que moi qui pietine )

  12. #9
    Ledescat

    Re : Problème d'arithmetique

    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 ?
    Cogito ergo sum.

  13. #10
    Deeprod

    Re : Problème d'arithmetique

    Citation Envoyé par Ledescat Voir le message
    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

  14. #11
    Taar

    Re : Problème d'arithmetique

    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.

  15. #12
    Gpadide

    Re : Problème d'arithmetique

    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 !!

  16. Publicité
  17. #13
    Gwyddon

    Re : Problème d'arithmetique

    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.
    A quitté FuturaSciences. Merci de ne PAS me contacter par MP.

  18. #14
    Taar

    Re : Problème d'arithmetique

    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.

  19. #15
    homotopie

    Re : Problème d'arithmetique

    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

  20. #16
    ericcc

    Re : Problème d'arithmetique

    Citation Envoyé par ericcc Voir le message
    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
    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.

Discussions similaires

  1. Problème d'arithmétique
    Par Tix dans le forum Mathématiques du collège et du lycée
    Réponses: 4
    Dernier message: 20/10/2006, 05h35
  2. Probleme d'arithmétique
    Par Blog dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 10/03/2005, 17h00
  3. probleme d'arithmetique, TS
    Par planck dans le forum Mathématiques du supérieur
    Réponses: 5
    Dernier message: 24/02/2005, 21h17
  4. Problème d'arithmétique
    Par g_h dans le forum Mathématiques du supérieur
    Réponses: 7
    Dernier message: 28/12/2004, 21h11
  5. problème d'arithmétique.
    Par baryon dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 10/11/2004, 15h41