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

Un exercice d'arithmétique

Envoyé par mustapha 
Un exercice d'arithmétique
il y a six mois
Bonjour chers collègues, est-ce que quelqu'un a une piste ou une idée pour traiter l'exercice suivant.

Soit $f$ une bijection de $\mathbb N^*$ vers lui-même, montrer qu'il existe trois entiers naturels non nuls tels que $a<b<c$ et $2f(b)=f(a)+f(c)$.
Merci.



Edité 1 fois. La derni&egrave;re correction date de il y a six mois et a &eacute;t&eacute; effectu&eacute;e par AD.
Re: un exercice d'arithmétique
il y a six mois
Bonjour. On peut manipuler plutôt la fonction réciproque de $f$, notée $g$ et même prendre $a=1=g(a')$
Re: un exercice d'arithmétique
il y a six mois
avatar
Mes réflexions à chaud sur le sujet si je l'ai bien compris:

Si on choisit $a,c$ tels que $f(a)+f(c)$ est pair* alors $\frac{f(a)+f(c)}{2}$ est un entier et si on prend $b=f^{-1}\left(\frac{f(a)+f(c)}{2}\right)$ on montre qu'on a $a,b,c$ tels que $2f(b)=f(a)+f(c)$
Je suis bien d'accord que, a priori, on n'a pas $a<b<c$ autrement cette question est trop simple.

* on prend deux nombres pairs, par exemple, et $a,c$ sont leur image réciproque respective.

Je vis parce que les montagnes ne savent pas rire, ni les vers de terre chanter.(Cioran)
Re: un exercice d'arithmétique
il y a six mois
En passant à l'application réciproque, le problème se ramène à montrer que toute bijection de $ {\mathbf N}^*$ est croissante sur au moins une suite arithmétique à trois termes.
Re: un exercice d'arithmétique
il y a six mois
Bonjour,

À mon avis il faudrait choisir le $a$ tel que $f(a) =1$, considérez l'ensemble $E$ des entières $n$ tels que $f(n)$ est impair, et essayer d'obtenir une contradiction en supposant le contraire, qui s'obtient à mon avis en montrant que $E$ serait nécessairement de cardinal fini.
Re: un exercice d'arithmétique
il y a six mois
Tentative.

Soit $f$ : ${\mathbf N}^* \rightarrow {\mathbf N}^*$ une bijection. On doit montrer que $f$ est croissante sur une progression arithmétique à trois termes : il existe $a$, $b>0$ tels que $f(a) <f(a+b)<f(a+2b)$.

Raisonnons par l'absurde. Posons $a=f(1)$. Il existe $N>0$ tel que pour tout $n\geqslant N$, $f(1+n) >a=f(1)$ (sinon il existerait une infinité de $n$ tels que $f(n)\in [1,a]$, ce qui contredirait l'injectivité de $f$). La progression $1$, $1+n$, $1+2n$ étant arithmétique, on doit avoir $f(1+2n)<f(1+n)$, pour tout $n\geqslant N$. Ainsi la suite $f(1+2^k N)$, $k\geqslant 0$, est une suite d'entiers positifs strictement décroissante, ce qui bien sûr n'existe pas (toute partie non vide de $\mathbf N$ ayant un minimum).
Re: un exercice d'arithmétique
il y a six mois
Désolé, en écrivant ce que je proposais je ne conclus pas.
On raisonne par l'absurde.
$E$ défini dans le précédent post.
$\forall n\in E$ soit $x_n$ l'unique entier tel que $(1+f(n))/2=f(x_n)$ qui vérifie donc $x_n>=n$, et avec les hypothèses $x$ est injective donc réalisé une bijection de $E$ sur $x(E)$.
À partir de là, je ne vois pas.

Piste
Si on sait montrer qu'il n'existe pas de bijection telle que (correction) $f(a_n)=(1+f(n)) /2$ quel que soit $ a_n>=n$ où $a_n$ est une suite à valeurs dans $N$...ça a l'air raisonnable.



Edité 3 fois. La derni&egrave;re correction date de il y a six mois et a &eacute;t&eacute; effectu&eacute;e par side.
Re: un exercice d'arithmétique
il y a six mois
En mode vraiment pas compliqué: ça a l'air de fonctionner avec $a=1$, $b$ le plus petit élément tel que $f(b)>f(1)$ (ça existe, c'est un bon ordre), et l'élément $c$ qui vérifie $f(c)=2f(b)-f(1)$ est nécessairement plus grand que $b$ puisque $2 f(b) -f(1) > f(b) > f(1)$.
Re: un exercice d'arithmétique
il y a six mois
Je viens de constater que du coup, ça fonctionne aussi avec n'importe quel $a$ tel que $\forall n [n<a \rightarrow f(n)<f(a)]$.
Re: un exercice d'arithmétique
il y a six mois
avatar
Titi le curieux:

J'ai l'impression que tu dissimules sous le tapis un argument en brandissant la justification: "Il existe un plus petit élément $b$, tel que $f(b)>f(1)$ (ça existe c'est un bon ordre)". Argument, me semble-t-il, développé par ceux qui ont posté juste avant toi.

Je vis parce que les montagnes ne savent pas rire, ni les vers de terre chanter.(Cioran)



Edité 1 fois. La derni&egrave;re correction date de il y a six mois et a &eacute;t&eacute; effectu&eacute;e par Fin de partie.
Re: un exercice d'arithmétique
il y a six mois
Euh... non... ou alors, pas consciemment... Je répond naïvement à la question du départ avec les outils que je connais et j'ai l'impression que ça tourne pas trop mal. Il fallait ajouter que la partie de $\mathbb{N}^*$ contenant les éléments $n$ tel que $f(n)>f(1)$ a de bonne grosse chance d'être non vide si f est une bijection de $\mathbb{N}^*$ dans lui-même?



Edité 1 fois. La derni&egrave;re correction date de il y a six mois et a &eacute;t&eacute; effectu&eacute;e par Titi le curieux.
Re: un exercice d'arithmétique
il y a six mois
avatar
Et on revient aux démonstrations produites par tes prédécesseurs qui me semble-t-il, en substance, prouvent des trucs similaires à ce que tu affirmes.

PS:
Note bien, que ta version est peut-être la plus intuitive.

Je vis parce que les montagnes ne savent pas rire, ni les vers de terre chanter.(Cioran)



Edité 1 fois. La derni&egrave;re correction date de il y a six mois et a &eacute;t&eacute; effectu&eacute;e par Fin de partie.
Re: un exercice d'arithmétique
il y a six mois
Je viens de lire en détail les réponses et en particulier celle de Paul Broussous... ok... Je ne pigeais pas cette histoire "d'argument passé sous le tapis", que j'ai pris très littéralement (je me suis dit que c'était bizarre de vouloir plus de détail), je suis désolé, ce n'était pas une tentative d'appropriation pour le côté "bijection et bon ordre", qui me semblait suffisamment intuitif pour ne pas en parler (je suis globalement assez ignare en math, mais j'ai notamment fait Peano en mode assez détaillé et je crois que même sans ça, ça ce serait plutôt bien passé). Cela dit, c'est vrai que j'aurais pu me passer de sortir le bon ordre et me contenter d'afficher la solution.
Re: un exercice d'arithmétique
il y a six mois
avatar
Quand tu dis que l'ensemble des entiers $n$ qui sont tels que $f(n)>f(1)$ est non vide.

Je pense immédiatement à une preuve par l'absurde (comme les autres personnes qui se sont essayées à publier une preuve, me semble-t-il):

La négation de cette proposition est que pour tout $n$ entier naturel on a $f(n)\leq f(1)$
Comme $f$ est une bijection tous les entiers $f(n)$ sont distincts et ils sont en nombre infini.
Mais il y a un nombre fini d'entiers qui sont inférieurs ou égaux à un entier donné fixé ce qui est une contradiction.

Je vis parce que les montagnes ne savent pas rire, ni les vers de terre chanter.(Cioran)
Re: un exercice d'arithmétique
il y a six mois
??? ... euh... ça devient étrange... pourquoi vous dites ça?

Déjà, je ne vois absolument pas où on va avec cette histoire d'absurde (l'est-elle?), d'autre part, certes, je vais utiliser l'absurde à un moment ou un autre (par exemple, si je pars des axiome de Peano et que j'ai déjà obtenu pas mal de truc sur l'addition, j'aurais tendance à le faire pour montrer que je peux définir une relation d'ordre totale sur $\mathbb{N}$ sur la base de l'addition puis pour montrer que c'est un bon ordre, expression que j'ai utilisé).
Une fois que j'ai le bon ordre que je sais que quelque tout élément est majoré par (une petite infinité) d'autres et que f est bijectif (donc surjectif) je ne vois pas pourquoi je devrais faire un raisonnement par l'absurde pour, d'une part qu'il y a des éléments $n$ tel que $n>f(1)$ et d'autre part qu'il y a des éléments $k$ de $\mathbb{N}$ tel que $f(k)$ est égal à l'un ou l'autre de ces éléments (là, je commence à soupçonner que j'ai un ensemble pas trop vide) enfin cet ensemble possède un plus petit élément (j'ai parlé de bon ordre! zut!). J'ai des outils, je les utilise comme je peux (si j'en ai besoin et que je trouve ça pratique), sinon, c'est casse-bonbons et je ne vois pas pourquoi je me ferais suer à apprendre des trucs (non mais! vilain dictateur! fais gaffe à pas m'embêter avec des trucs bof pertinents, sinon je deviens pas cool! angry smiley).
Re: un exercice d'arithmétique
il y a six mois
avatar
Vous affirmez quelque chose j'essaie de me convaincre par un raisonnement que c'est vrai parce que la phrase:
"ça existe, c'est le bon ordre" ne me convainc pas trop et j'en suis désolé.

Je vis parce que les montagnes ne savent pas rire, ni les vers de terre chanter.(Cioran)
Re: un exercice d'arithmétique
il y a six mois
C'était ça? J'explique: l'existence d'une partie non vide de $\mathbb{N}$ dont chaque élément est d'image par f plus grand que f(1) me semblait évident dés lors que f est surjectif, la parenthèse était là pour préciser que cet ensemble possède un plus petit élément qui correspond à $b$ (car si on n'avait pas cette propriété, ce serait la galère pour montrer la propriété désirée parce qu'il serait difficile de désigner un $b$ qui convient, je soupçonne même que la propriété serait généralement fausse, j'ai donc pensé que ce point précis était important). Ok, c'était vite dit, désolé, mais là, je me contentais de balancer une manière toute bête de désigner une solution, vu que le public de ce forum est beaucoup plus instruit que moi sur les maths en général je ne pouvais pas imaginer qu'on allait galérer pour montrer l'existence d'un truc aussi basique, ce n'était pas le sujet (pour plus de précision: 1 désignait le plus petit élément de $\mathbb{N}^*$ et vu que la conversation est classée en algèbre, $\mathbb{N}^*$ est une écriture abusive pour désigner $\mathbb{N}\backslash \{ 0 \}$ vu qu'il n'y a pas d'élément symétrisable par l'une des deux "opérations canoniques" dans $\mathbb{N}$. Ça va comme ça? grinning smiley).

P.S: j'ai peut-être été un peu sec sur la fin, mais peut-être qu'il y a juste un petit problème de vocabulaire, bien que ça me surprendrait.



Edité 1 fois. La derni&egrave;re correction date de il y a six mois et a &eacute;t&eacute; effectu&eacute;e par Titi le curieux.
Re: un exercice d'arithmétique
il y a six mois
avatar
Donc si tu me dis:
je considère la partie de $\mathbb{N}$ telle que $n$ appartient à cette partie si et seulement si $f(n)>f(1)$.
Pour pouvoir affirmer qu'il y a un plus petit élément, parce que $\mathbb{N}$ est bien ordonné il faut vérifier préalablement que cette partie est non vide.
Et j'ai la nette impression que pour montrer que cette partie est non vide on a besoin du fait que $\mathbb{N}$ n'est pas fini et donc que la propriété du bon ordre seule n'est pas suffisante.
Tout cela pour dire que cette affirmation demande tout de même une explication qui va au-delà du lapidaire: "c'est la propriété du bon ordre".

PS:
Si on considère la partie de $\mathbb{N}$ composée de $1,2,3,4,5$ munie de l'ordre ordinaire. Si $f$ est une bijection de cet ensemble l'ensemble des $n$ de cette partie qui vérifient $f(n)>5$ n'est pas tellement rempli. smoking smiley

PS2:
Hormis cette petite critique ta démonstration est chouette.

Je vis parce que les montagnes ne savent pas rire, ni les vers de terre chanter.(Cioran)



Edité 4 fois. La derni&egrave;re correction date de il y a six mois et a &eacute;t&eacute; effectu&eacute;e par Fin de partie.
Re: Un exercice d'arithmétique
il y a six mois
avatar
A la rescousse de Titi le curieux.

P.S. $b$ existe car il n'y a qu'un nombre fini de places avant $f(1)$.



Edité 1 fois. La derni&egrave;re correction date de il y a six mois et a &eacute;t&eacute; effectu&eacute;e par soland.


Re: un exercice d'arithmétique
il y a six mois
Merci beaucoup Soland, c'est très sympa, mais pas trop nécessaire. En fait si la raison que tu invoques (le coup du nombres finis de places) est vrai dans $\mathbb{N}$, la propriété qui était à démontrer est vrai dans d'autres ensembles plus compliqués, dont un exemple simple est $\mathbb{N}^2$ munie de l'addition "habituelle" et d'une relation d'ordre de type $\forall (a,b),(c,d)[(a,b)\leq (c,d) \leftrightarrow a<c \lor (a=c \wedge b\leq d)]$ et en définissant $2(a,b)=(2a,2b)$, et pour les raisons que j'ai invoquées (alors que ce coup là, $f( (0,1))$ est susceptible de présenter une infinité d'élément plus petit que lui).

@Fin de Partie:
Tu constateras qu'il y a un message dans lequel je dis d'une part que je suis susceptible de ne pas être cool et d'autre part où je précise un certain nombres de propriétés de $\mathbb{N}$ parmi lesquels le fait que chaque éléments est majoré (je crois que ça se dit "il n'y a pas d'élément maximal", je dis aussi qu'une fois que j'ai tout ça, je me passe bien de l'absurde pour démontrer ce qu'il y a à trouver, je maintiens). Étrange que je cite cette propriété en particulier plutôt que des trucs sur la multiplication ou les nombres premiers. Peut-être bien que c'est parce que je considérais que c'était une propriété utile pour la démonstration (ou alors je suis complétement marteau et j'ai eu sacré coup de bol). Dans le doute, ton histoire d'ensemble fini, tu aurais bien fait de te la garder, ça prouve juste que tu fais des fixettes et n'essaies pas de comprendre ton interlocuteur. Merci quand même pour l'appréciation de l'idée de base.
Re: un exercice d'arithmétique
il y a six mois
avatar
La relation de bon ordre sur $\mathbb{N}$ c'est $\leq$ et pas $<$.

Donc, dans la démonstration [www.les-mathematiques.net]
La conclusion est que $c\geq b$.
Ce n'est pas exactement ce qu'on voulait.

Je vis parce que les montagnes ne savent pas rire, ni les vers de terre chanter.(Cioran)
Re: un exercice d'arithmétique
il y a six mois
Merci pour la précision concernant la définition, je reconnais ne pas toujours faire très attention entre les ordres et les ordres stricts. La conclusion me fais un peu plus rigoler, mais bon, je suppose que tu n'as pas choisis un pseudo comme "fin de partie" pour rien, alors je concède.
Re: Un exercice d'arithmétique
il y a six mois
C'était pas un exo du concours général ? Il me semble l'avoir déjà vu quelque part.
Re: un exercice d'arithmétique
il y a six mois
Merci Paul Broussous , je trouve génial votre méthode .
Re: Un exercice d'arithmétique
il y a six mois
c'est un exercice des oraux X et je pense aussi olympiade
Re: Un exercice d'arithmétique
il y a six mois
Il me semble qu'il existe même une suite (au moins) infinie a1 < a2 < a3 < a4......telle que 2* f(a(2k)) = f(a(2k-1)) + f(a(2k+1))
Re: Un exercice d'arithmétique
il y a six mois
@nodgim: J'ai l'impression que la bijection suivante par exemple ne montre pas de telle suite infinie (en revanche, elle présente clairement des suites finies aussi longues que l'on veut, mais je ne suis pas certain que c'est une propriété systématiquement vérifiée):
$f$ définie par $\forall n \in \mathbb{N}:f(2^n)=2^n$ et (si n>1) $\forall k\in |[2^n+1,2^{n+1}-1]|$: $f(k)=2^{n+1}+2^n-k$ (c'est à dire que c'est une bijection décroissante sur "l'intervalle" considéré).

P.S: Oups! Hors-sujet, je n'avais pas fait attention aux "2" devant les "k", désolé. Du coup, oui, je suis complétement d'accord, tu peux par exemple prendre a(1)=1 et par la suite a(2k) = le plus petit entier $n$ plus grand que a(2k) tel que $\forall l (l<n\rightarrow f(l)<f(n))$ et celui qui passe bien pour a(2k+1).



Edité 3 fois. La derni&egrave;re correction date de il y a six mois et a &eacute;t&eacute; effectu&eacute;e par Titi le curieux.
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: 138 418, Messages: 1 343 977, Utilisateurs: 24 829.
Notre dernier utilisateur inscrit Azaborn.


Ce forum
Discussions: 5 136, Messages: 62 260.

 

 
©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