Juste de la logique...
dans Arithmétique
Soit f une application de IN* dans IN* telle que pour tout entier naturel n non nul, on a : f(f(n))<f(n+1).
Montrer que pour tout entier naturel n, on a : f(n)=n.
Montrer que pour tout entier naturel n, on a : f(n)=n.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Regardez le sixième problème des IMO 1977 à Belgrade.
Sinon, je veux pas casser l'énigme donc je ne mets pas les "si; donc; ..." mais propose un enchainement comme indice:
$t+1\geq a+1$ et $a+1>f(t+1)$ =>
$ a+1 >f(t+1)>f(f(t))$ =>
$ a>f(f(t))$ ( => ) $a>f(t) $ ...
Ah, remarque, peut-être que le $\exists$ qui intervient d'une manière précise, tu considères ça comme de la logique?
Maintenant que j'ai écrit ça, ça devient de la logique de rédiger
f(n)=n+a est aussi solution... Est ce que f doit etre bijective?
Enfin du moins c'est l'indice que j'ai donné, mais il n'est pas clair qu'il existe une solution calculatoire d'un autre style.
Toutes mes excuses SXB...
> f(n)=n+a est aussi solution...
Pas vraiment : si \(f(n) = n+a\), alors \(f(f(n)) = n+2a\) et \(f(n+1) = n+1+a\) ; la condition \(f(f(n))<f(n+1)\) impose donc \(a<1\), c'est-à-dire \(a=0\).
(On a $f(f(n))=f(n+a)=n+2a$ et $f(n+1)=n+1+a$, et donc on doit avoir $2a<a+1$)
Bon je mets juste ma solution de ce matin rédigée, mais après je la colorerai en blanc, c'est juste pour vérifier que je ne fais perdre de temps à personne avec l'indice:
Soit $n$ le premier entier tel que $f(n)\neq n$. Admettons qu'il s'écrive $p+1$. ***
alors $p=f(p)$ et $f(p+1)>f(f(p))=p$ donc $f(n)>n$. Soit $a:=f(n)$. alors $f(n+1)>f(a)$ et pourtant $a\geq n+1$
Il s'ensuit qu'il existe $a$ et $b$ tel que $a\geq b$ et $b>f(a)$.
Soit alors $n$ le premier entier tel qu'il existe $t$ avec $t\geq n$ et $n>f(t)$. En écrivant $n=m+1$ et $t=u+1$, on obtient que $u\geq m$. Par ailleurs, $m+1>f(u+1)>f(f(u))$ donc $m>f(f(u))$ et comme $m+1$ est le plus petit blabla, c'est que $m>f(u)$, mais alors contradiction (car $u\geq m$)
Dans ***, j'ai triché en supposant que n n'est pas 1, mais bon ça laisse un trou à boucher et de toute façon ça me fait tellement mal au crâne...
(f o f)(n) <(f o g)(n)
il est clair que f(n) est différent de g(n) (inégalité strict), alors
Soit f(n) > g(n), mais comme (f o f)(n) <(f o g)(n) cela signifie que f(n) est strictement décroissante, ce qui est impossible sur N
Soit f(n) < g(n) => f(n)<n+1 => f(n) = n ou f(n)=min(IN) or f(n) est différent de 0. Aussi f(n) = n.
j'ai bon ?
1 - f(n) ne saurait être constante ou partiellement constante (à partir de n0 f(n) est constante) sinon l'inégalité strict ne peut pas s'appliqué en tout n
2 - une faute de frappe, il faut lire
Soit f(n) < g(n) => f(n) < n+1 => f(n) = n.
Souvenirs, souvenirs: par exemple... http://www.les-mathematiques.net/phorum/read.php?5,328155,328155#msg-328155
Cet IMO est proposé au moins une fois chaque année sur notre forum.
Amicalement.
> mamane
J'ai du mal à te suivre car tu commences par "pour tout n", mais ensuite tu ne distingues que deux cas f<g ou f>g. Le sens de l'inégalité peut très bien varier selon les valeurs de n. Mais bon, peut-être que quelque chose m'échappe...
Je propose ceci :
L'ensemble des images possède un plus petit élément f (k).
Supposons que k soit différent de 1.
Alors f(f(k-1)) < f(k) ce qui contredit le fait que f(k) soit la plus petite image.
Donc f(1) est la plus petite image.
Le même raisonnement montre en outre que l'image f(1) n'est atteinte qu'une fois :
s'il existait k différent de 1 tel que f(k) = f(1), alors f(f(k-1)) < f(k) c'est à dire f(1) ce qui contredit le fait que f(1) soit la plus petite image.
Ecartons f(1) de l'ensemble des images et soit f(m) la plus petite image restante.
Nous savons que m est différent de 1 puisque f(1) a été écarté.
Supposons que m soit différent de 2.
Alors f(f(m-1)) < f(m), ce qui contredit le fait que f(m) soit la plus petite image restante puisque nous savons que f(m-1) ne peut pas être égal à f(1).
Le même raisonnement qu'au-dessus nous montre que l'image f(2) n'est atteinte qu'une fois.
On peut poursuivre avec f(3), f(4) etc.
On a donc un isomorphisme d'ordre de N sur f(N) : si a < b, alors f(a) < f(b)
On observe que, pour tout n, f(n) ne peut pas être plus petit que n.
Supposons qu' il existe p avec f(p) différent de p.
Donc f(p) > p
Donc f(f(p) < f(p+1) (d'après l'énoncé), mais aussi f(f(p) > f(p) (comme nous l'avons montré).
Or, dans la suite croissante des images, il n'y a aucune place entre f(p) et f(p+1).
Donc, quel que soit p, f(p) = p.
Aldo.
1) prouver que $\forall x,y:x\geq y\to f(x)\geq y$ (aide montrer que l'ensemble des $x$ tels que $\exists y: y\geq x$ et $x>f(y)$ n'a pas de minimum
2) en déduire le résultat
Ce découpage rend l'exo facile, l'aspect "logique" de la question étant la considération de l'ensemble $A:=\{x/\exists y: blabla \}$
Aldo.