[MPSI] Problème de bijection

Aide à la résolution d'exercices ou de problèmes de niveau Supérieur.

Modérateur: gdm_aidesco

Règles du forum
Merci d'éviter le style SMS dans vos messages et de penser à utiliser la fonction Recherche avant de poster un message. Pour joindre des fichiers à vos messages, consulter ce sujet.
> Penser à utiliser le mode LaTeX (voir ici) afin de rendre vos formules plus lisibles.
> Ne poster qu'un exercice (ou problème) par sujet et indiquer son niveau précis dans le titre du message.

[MPSI] Problème de bijection

Messagepar Odward » Dimanche 08 Octobre 2006, 17:08

Bonjour,

on veut de montrer qu'il existe "autant d'éléments" dans $\N$ que dans $\N^2$
Pour cela on se propose d'étudier la bijectivité de l'application :

$g:\left\{\begin{array}{l}\n \N^2 \rightarrow \N \\ \n (m,n) \rightarrow 2^m(2n+1)-1 \n \end{array}\right.}$

J'ai tout d'abord tenté de trouver l'application réciproque de $g$ pas un raisonnement d'analyse-synthèse mais ne sachant pas comment le faire avec deux variables je n'y suis pas arriver.

Je me suis alors dit qu'il fallait peut être faire la démonstration en deux étapes : l'injectivité puis la surjectivité.


Pour l'injectivité ça donne :


Soient $(m,n),(m',n') \in \N^2$. Supposons $g(m,n)=g(m',n')$

ie $2^m(2n+1)-1=2^m'(2n'+1)-1$

Comme $m$ et $m'$ jouent un rôle symetrique on peut supposer que $m \ge m'$

ie $2^m^-^m'(2n+1)=2n'+1$

ie $m=m'$ et $2n+1=2n'+1$ (car $2n+1$ et $2n'+1$ sont impairs donc $2^m^-^m'$ ne peut être pair d'où $m=m'$)

ie $(m,n)=(m',n')$


Pour la surjectivité :


Soit $k\in\N$. Montrons qu'il existe un couple $(m,n)$ tel que $k=g(m,n)$.

C'est à partir d'ici que vient le problème : j'essaye de raisonnement par un analyse-synthèse pour trouver un résultat mais je n'y arrive pas.

Synthèse :

$k=g(m,n)$

ie $k=2^m(2n+1)-1$

Je raisonne par disjonction de cas :

Si $k$ est pair alors il existe un $k'\in\N$ tel que $k=2k'$
d'où $k=2^0(2k'+1)-1$

Si $k$ est impair alors il existe un $k'\in\N*$ tel que $k=2k'-1$
d'où $k=2^1(k')-1$

Et là il faut encore faire une disjonction de cas si k' est pair ou impair ... et je ne vois pas trop comment je peux faire.

J'ai l'impression que ce n'est pas la bonne méthode et j'aimerai que vous m'aidiez.

Merci d'avance
Odward
Déca-utilisateur
 
Messages: 15
Inscription: Dimanche 01 Octobre 2006, 17:02
Localisation: Paris

Publicité

Messagepar Odward » Dimanche 08 Octobre 2006, 18:12

Je réfléchi encore est je n'y arrive toujours pas : il faudrait que je fasse la disjonction d'une infinité de cas.

Je sais que quand $m=0$ et $n$ varie dans $\N$ alors je recupére tout les nombres pairs avec $g(0,n)$

Si $g$ est bijective de $\N^2$ sur $\N$ alors forcement quand $m \ne 0$ $g(m,n)$ devrait décrire l'ensemble des impairs.

Donc le faite que $m \ne 0$ devrait mettre utile dans les calculs pour montrer que $g(m,n)$ décrit les impairs : je pourrai peut être faire comme si $m$ était fixe et alors utiliser la racine $m^i^ème$ et après fixer $n\dots$


Je ne sais plus trop quoi faire et dans quelle direction aller !
Odward
Déca-utilisateur
 
Messages: 15
Inscription: Dimanche 01 Octobre 2006, 17:02
Localisation: Paris

Messagepar Odward » Dimanche 08 Octobre 2006, 18:26

Est-ce que vous me boudez ?

Je voudrai juste un coup de main dans la refléxion qui pourra m'aider à trouver la réponse nullement la réponse ... Ca doit faire 5h en tout que je suis sur la question et pensez bien que ça ne m'interresse vraiment pas d'avoir juste la reponse ... Faites moi juste un signe pour me montrer que vous avez lu mon message même si vous n'avez strictement aucune idée de la technique de résolution de ce problème.

Merci encore
Odward
Déca-utilisateur
 
Messages: 15
Inscription: Dimanche 01 Octobre 2006, 17:02
Localisation: Paris

Messagepar MB » Dimanche 08 Octobre 2006, 18:34

Odward a écrit:Est-ce que vous me boudez ?


Non, pas du tout !

Je viens de me regarder ton exercice là. Pour l'instant je suis d'accord avec ce que j'ai lu. La méthode me semble correcte et l'injectivité est bien prouvée.

Il est également clair que si $k = 2k'$ est un nombre pair alors $m=0$ et $n=k'$ convient.

On suppose maintenant que $k$ est impair.

Puisque $k$ est impair, on peut écrire $k = k' - 1$, $k'$ étant un nombre pair.

On peut alors écrire $k' = 2^a \times k''$, $k''$ étant un nombre impair et $a \neq 0$.

Puisque $k''$ est impair, il peut s'écrire $k'' = 2b +1$.

Au final, on a donc :

$$ k = 2^a (2b+1)-1 $$



Donc $m=a$ et $n=b$ conviennent.
MB
Administrateur
 
Messages: 6892
Inscription: Samedi 28 Mai 2005, 13:23
Localisation: Créteil
Statut actuel: Actif et salarié | Enseignant

Messagepar Odward » Dimanche 08 Octobre 2006, 19:00

et donc le fait que $m \ne 0$ s'utilise pour justifier que $k'=2^ak''$ en disant que ainsi $2^a$ est bien pair vu que $a \in \N^*$

Pour le cas $k=1$ il est trivial que le couple $(1,0)$ marche ...

Maintenant que l'analyse est terminé il va falloir que je me lance dans toute la partie synthèse ...

Merci encore pour le coup de pouce
Odward
Déca-utilisateur
 
Messages: 15
Inscription: Dimanche 01 Octobre 2006, 17:02
Localisation: Paris

Messagepar MB » Dimanche 08 Octobre 2006, 19:26

Odward a écrit:et donc le fait que $m \ne 0$ s'utilise pour justifier que $k'=2^ak''$ en disant que ainsi $2^a$ est bien pair vu que $a \in \N^*$


On n'utilise pas le fait que $m \neq 0$. On constate simplement qu'il est différent de 0 puisque $m=a \neq 0$.

Odward a écrit:Pour le cas $k=1$ il est trivial que le couple $(1,0)$ marche ...


Il n'y a pas besoin de traiter le cas $k=1$ à part en fait.
MB (Pas d'aide en Message Privé)
Merci d'utiliser $\LaTeX$ (voir ici) et d'éviter le style SMS pour la lisibilité des messages.
MB
Administrateur
 
Messages: 6892
Inscription: Samedi 28 Mai 2005, 13:23
Localisation: Créteil
Statut actuel: Actif et salarié | Enseignant

Messagepar kilébo » Dimanche 08 Octobre 2006, 21:41

Pour la surjectivité, considérons $k \in \N$.

$k + 1 > 0$ se décompose de la façon suivante : $k + 1 = 2^m \time p$ avec $p$ impair. Il reste plus qu'à poser $p = 2n+1$ et tu as la surjectivité.

Tu remarqueras qu'en fait, tu aurais pu obtenir la bijection directement avec le même argument.
kilébo
Téra-utilisateur
 
Messages: 1059
Inscription: Samedi 22 Avril 2006, 11:08
Localisation: Région Parisienne
Statut actuel: Actif et salarié

Messagepar MB » Dimanche 08 Octobre 2006, 21:48

Oui, c'est clair qu'il s'est compliqué la vie. :wink:
MB (Pas d'aide en Message Privé)
Merci d'utiliser $\LaTeX$ (voir ici) et d'éviter le style SMS pour la lisibilité des messages.
MB
Administrateur
 
Messages: 6892
Inscription: Samedi 28 Mai 2005, 13:23
Localisation: Créteil
Statut actuel: Actif et salarié | Enseignant

Messagepar nirosis » Dimanche 08 Octobre 2006, 21:50

Odward devrait être montré en exemple. Je viens de tomber sur ce post.
Mais l'effort de rédaction, l'utilisation de latex est assez plaisante !!
Si tout le monde pouvait en faire autant :wink:

n'hésite pas à revenir Odward ! désolé pour le temps de réponse, mais on est pas tout le temps sur le forum ;)
nirosis
Administrateur
 
Messages: 1806
Inscription: Samedi 28 Mai 2005, 13:48
Localisation: Orsay, France
Statut actuel: Actif et salarié | Maître de conférence

Messagepar Odward » Lundi 09 Octobre 2006, 17:00

kilébo a écrit:Pour la surjectivité, considérons $k \in \N$.

$k + 1 > 0$ se décompose de la façon suivante : $k + 1 = 2^m \time p$ avec $p$ impair. Il reste plus qu'à poser $p = 2n+1$ et tu as la surjectivité.

Tu remarqueras qu'en fait, tu aurais pu obtenir la bijection directement avec le même argument.


Je suis totalement d'accord avec le raisonnement mais je ne pense pas avoir le droit d'utiliser la propriété sur la décomposition de $k+1=2^mp$ avec $p$ impair.

Ce problème reste un problème mathématique ''scolaire'' : je n'ai pas la preuve que cette décomposition est possible(enfin à ma connaissance).
Donc je ne pense pas que je puisse utiliser ce résultat sans l'avoir démontré.
Alors que dire qu'un nombre pair $k$ peut s'écrire sous la forme $2^ak''$ avec $k''$ impair, doit m'être autorisé autorisé car il est trivial que dans la décomposition en facteur premier d'un nombre pair on retrouve $a$ fois 2 (ou $a \ne 0$) fois, forcement, un nombre impair car tout les nombres premiers à part 2 sont impairs (résultat lui démontré).

Par contre si je m'amuse à démontrer le résultat donné normalement ca devrait pouvoir passé dans la rédaction...

Merci tout de même et merci à nirosis pour l'invitation à de nouveau post ... je pense que j'en aurai souvent l'occasion ;)
Dernière édition par Odward le Lundi 09 Octobre 2006, 22:41, édité 1 fois.
Odward
Déca-utilisateur
 
Messages: 15
Inscription: Dimanche 01 Octobre 2006, 17:02
Localisation: Paris

Messagepar MB » Lundi 09 Octobre 2006, 17:32

Odward a écrit:Je suis totalement d'accord avec le raisonnement mais je ne pense pas avoir le droit d'utiliser la propriété sur la décomposition de $k+1=2^mp$ avec $p$ impair.

Ce problème reste un problème mathématique ''scolaire'' : je n'ai pas la preuve que cette décomposition est possible (enfin à ma connaissance).
Donc je ne pense pas que je puisse utiliser ce résultat sans l'avoir démontré.


N'importe quel entier peut s'écrire sous la forme $2^m \times p$ avec $m \geq 0$ et $p$ impair. Il n'y a aucune différence avec la propriété que tu utilises par la suite.
MB (Pas d'aide en Message Privé)
Merci d'utiliser $\LaTeX$ (voir ici) et d'éviter le style SMS pour la lisibilité des messages.
MB
Administrateur
 
Messages: 6892
Inscription: Samedi 28 Mai 2005, 13:23
Localisation: Créteil
Statut actuel: Actif et salarié | Enseignant


Retourner vers Exercices et problèmes : Supérieur

 


  • Articles en relation
    Réponses
    Vus
    Dernier message

Qui est en ligne

Utilisateurs parcourant ce forum: Bing [Bot] et 3 invités