Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
125 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Juste de la logique...

Envoyé par SXB 
SXB
Juste de la logique...
il y a neuf années
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.
Re: Juste de la logique...
il y a neuf années
avatar
Bonjour,

Regardez le sixième problème des IMO 1977 à Belgrade.
Re: Juste de la logique...
il y a neuf années
à SXB pourquoi tu as titré "juste de la logique"? Il me semble que ce genre de devinettes se résout avec pas spécialement plus "de logique" qu'un problème de maths "habituel" non?

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))$ ( :D => :D ) $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 :D
nico69
Re: Juste de la logique...
il y a neuf années
@ SXB :
f(n)=n+a est aussi solution... Est ce que f doit etre bijective?
Re: Juste de la logique...
il y a neuf années
Avant d'aller au dodo, je retire ce que j'ai dit et rends hommage à SXB qui a raison (pédagogiquement, et en les temps modernes): c'est bien un exo qu'on peut considérer comme emprunt d'une dose de logique (je viens de lire le deuxième post) pour des ados, puisqu'ils doivent, pour le résoudre, prendre le plus entier $n$ tel qu'il existe un entier p avec $p\geq n$ et $n>f(p)$ (le fait ensuite que si $f\neq id$ alors il existe un tel entier n est aisé je crois pour ces ados)

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...
gb
Re: Juste de la logique...
il y a neuf années
avatar
nico69 écrivait:
-------------------------------------------------------
> 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\).
Re: Juste de la logique...
il y a neuf années
avatar
Non, nico69, $f(n)=n+a$ n'est pas solution, sauf si $a<1$, i.e. $a=0$ (car $a$ est un entier positif, je suppose?).

(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$)

Greg

Ora, lege, lege, relege, labora et invenies (Prie, lis, lis , relis, travaille et tu trouveras)
Re: Juste de la logique...
il y a neuf années
à nico: (bon lol gb t'a répondu).

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 :D et de toute façon ça me fait tellement mal au crâne...
Re: Juste de la logique...
il y a neuf années
Ne lire que si vous n'avez pas envie de chercher (et en plus c'est sans garantie, c'est juste que je voulais vérifier que l'indice posté à la va vite ne déconnait pas), d'où le jaune (il suffit de sélectionner pour faite apparaitre...

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
mamane
Re: Juste de la logique...
il y a neuf années
si on pose g(n) = n+1 alors on a pour tout n de |N*

(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 ?
mamane
Re: Juste de la logique...
il y a neuf années
ça manque un peu de rigueur ce que j'ai mis

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.
bs
Re: Juste de la logique...
il y a neuf années
avatar
Bonjour,

Souvenirs, souvenirs: par exemple... [www.les-mathematiques.net]
Cet IMO est proposé au moins une fois chaque année sur notre forum.

Amicalement.



Edité 1 fois. La derni&egrave;re correction date de il y a neuf ann&eacute;es et a &eacute;t&eacute; effectu&eacute;e par bs.
Re: Juste de la logique...
il y a neuf années
Bonjour à tous,

> 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.
ccnc
Re: Juste de la logique...
il y a neuf années
En encre foncée,voici un découpage:


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 \}$
Re: Juste de la logique...
il y a neuf années
Dernier point d'interrogation : pourquoi a-t-on écarté le zéro ?

Aldo.
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 137 323, Messages: 1 329 156, Utilisateurs: 24 391.
Notre dernier utilisateur inscrit fonction.holomorphe.


Ce forum
Discussions: 5 092, Messages: 61 798.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page