Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 02-10-2019 17:46:29

Landry perter
Invité

Démontrer qu'une application est bijective

Salut j'aimerais savoir comment démontrer que l'application suivante est bijective: f définie de NxN dans N qui à tout (x,y) associe f(x,y)=(x+y)(x+y+1)/2 +y

#2 02-10-2019 19:19:37

kija
Membre
Inscription : 06-08-2019
Messages : 1

Re : Démontrer qu'une application est bijective

bonjour

fais un tableau à double entrée pour les petites valeurs de x et y.

Hors ligne

#3 02-10-2019 19:20:52

Lorenzo Empreur du sale
Invité

Re : Démontrer qu'une application est bijective

Salut, problème intéressant s'il en est.
Essaye de remplir le tableau suivant avec les valeurs de [tex]f(x,y)[/tex] histoire d'y voir un peu plus clair (colonne de gauche pour la variable $x$, ligne du haut pour la variable $y$) :

[tex]\begin{array}{|c|c|c|c|c|c|}
\hline
&0&1&2&3&4\\
\hline
0 &&&&&\\
\hline
1 &&&&\\
\hline
2 &&&\\
\hline
3 &&\\
\hline
4&\\
\hline
\end{array}[/tex]

(Inutile d'aller plus loin que la diagonale $x+y=4$)

#4 02-10-2019 21:41:45

Zebulor
Membre
Inscription : 21-10-2018
Messages : 367

Re : Démontrer qu'une application est bijective

Bonsoir,
On pourrait essayer de démontrer que [tex]f[/tex] est à la fois surjective et injective...
J'aurais tendance à poser x+y=k intuitivement car on reconnaît la somme des entiers de 1 à x+y ..mais...pas facile à première vue ...

Dernière modification par Zebulor (02-10-2019 21:47:25)

Hors ligne

#5 03-10-2019 14:53:22

Maenwe
Membre
Inscription : 06-09-2019
Messages : 79

Re : Démontrer qu'une application est bijective

Bonjour,

L'injectivité se fait plutôt simplement à coup d'inégalité et d'absurdité :
soit $(x,x_{1},y,y_{1}) \in \mathbb{N}^{4}$ tel que : $f(x,y)=f(x_{1},y_{1})$.
et quitte à échanger les indices on peut écrire : $x_{1}+y_{1} \leq x+y$.
Ainsi $\sum\limits_{k=x_{1}+y_{1}+1}^{x+y} k + y = y_{1}$.
Or si $x_{1}+y_{1} < x+y$ alors $\sum\limits_{k=x_{1}+y_{1}+1}^{x+y} k > y_{1}$ donc $\sum\limits_{k=x_{1}+y_{1}+1}^{x+y} k + y > y + y_{1} \geq y_{1}$.
Ce qui est absurde (car $0=0$) donc $x_{1}+y_{1} = x+y$, donc $y=y_{1}$ (car $\sum\limits_{k=x_{1}+y_{1}+1}^{x+y} k  = 0$).
Et puisque $x_{1}+y_{1} = x+y$ on a alors $x=x_{1}$

Dernière modification par Maenwe (03-10-2019 14:56:19)

Hors ligne

#6 04-10-2019 18:15:48

Maenwe
Membre
Inscription : 06-09-2019
Messages : 79

Re : Démontrer qu'une application est bijective

Bonsoir,

On peut éventuellement essayer de montrer que cette application est surjective en remarquant que : $f(x,y)+1=f(x-1,y+1)$ pour $x>0$ et :
$\mathbb{N}^{2}=\cup_{n\geq 0}  \{ (n-t,t) | t \in [|0,n|] \}$.

Dernière modification par Maenwe (04-10-2019 18:18:12)

Hors ligne

#7 04-10-2019 20:33:28

Zebulor
Membre
Inscription : 21-10-2018
Messages : 367

Re : Démontrer qu'une application est bijective

Bonjour,

@Maenwe : Je partais sur une autre piste : il existe toujours un entier compris entre la somme des p premiers entiers et la somme des p+1 premiers entiers..
Tes démonstrations sont séduisantes et celle sur la surjectivité est très subtile... mais j'ai du mal à te suivre parfois dans les enchaînements (est ce la vieillesse ?)
Tu écris :

Maenwe a écrit :

Ainsi $\sum\limits_{k=x_{1}+y_{1}+1}^{x+y} k + y = y_{1}$.

ca ne change peut être rien à ta démonstration mais est ce que ça ne serait pas plutôt : $\sum\limits_{k=x_{1}+y_{1}+2}^{x+y} k + y = y_{1} ? $
Car si j'ai bien compris tu retraduis là : [tex]f(x,y)=f(x_1,y_1)[/tex]
Ensuite je crois comprendre que tu conclus que l'hypothèse [tex]x+y>x_1+y_1[/tex] est fausse..
Alors tu écris :

Maenwe a écrit :

Ce qui est absurde (car $0=0$) donc $x_{1}+y_{1} = x+y$

, ce que je ne comprends pas...

Dernière modification par Zebulor (04-10-2019 20:57:16)

Hors ligne

#8 05-10-2019 08:52:32

Maenwe
Membre
Inscription : 06-09-2019
Messages : 79

Re : Démontrer qu'une application est bijective

Bonjour,

@Zebulor, Hmmm je suis peut-être allé un peu vite dans mes raisonnements je vais donc réécrire en un peu plus complet (je reprends les notations que j'ai adopté au début de mon raisonnement) :
$\frac{(x+y)(x+y+1)}{2}+y=\frac{(x_{1}+y_{1})(x_{1}+y_{1}+1)}{2}+y_{1}$
ce qui se réécrit : $\sum\limits_{k=1}^{x+y}k + y = \sum\limits_{k=1}^{x_{1}+y_{1}}k +y_{1}$ d'où :
$\sum\limits_{k=x_{1}+y_{1}+1}^{x+y}k + y = y_{1}$ (du coup je ne vois pas pourquoi ce serai $\sum\limits_{k=x_{1}+y_{1}+2}^{x+y}k + y = y_{1}$... Je loupe peut-être quelque chose ?).

NB : Si jamais il y a une erreur à ce niveau, si il y a un problème pour la suite, car l'hypothèse $y_{1}+x_{1} < x+y$ ne suffira pas à assurer que $y_{1}+x_{1}+2 \leq x+y$...

Ensuite, raisonnons par l'absurde et supposons que (j'ai relu mon argumentaire, et c'est vrai qu'il est un peu décousu je vais donc le réécrire pour qu'il soit plus complet et clair) : $y_{1}+x_{1} < x+y$.

On a donc $y_{1}+x_{1}+1 \leq x+y$, et ainsi : $\sum\limits_{k=x_{1}+y_{1}+1}^{x+y} k + y \geq x_{1} + y_{1} + 1 + y >x_{1} + y_{1} + y \geq y_{1}$. Donc $\sum\limits_{k=x_{1}+y_{1}+1}^{x+y} k + y > y_{1}$.

Ainsi $ y_{1} = \sum\limits_{k=x_{1}+y_{1}+1}^{x+y} k + y > y_{1}$ donc $y_{1} > y_{1}$ (ce qui revient à écrire $0>0$ ce qui est faux, enfin écrire $y_{1} > y_{1}$ est tout aussi clairement faux donc je me suis un peu embêté pour rien).
Donc $x_{1}+y_{1} = x + y$ (car si $x_{1}+y_{1} < x + y$ est faux cela signifie que $x_{1}+y_{1} \geq x + y$ or on a $x_{1}+y_{1} \leq x + y$, donc on a égalité).

Or on a $\sum\limits_{k=1}^{x+y}k + y = \sum\limits_{k=1}^{x_{1}+y_{1}}k +y_{1}$ donc $\sum\limits_{k=1}^{x+y}k - \sum\limits_{k=1}^{x_{1}+y_{1}}k+ y = y_{1}$ et donc (puisque $x_{1}+y_{1} = x + y$) $y=y_{1}$, et en réutilisant l'égalité $x_{1}+y_{1} = x + y$ on simplifie par $y$ et on obtient : $x_{1}$.

Elle a l'air intéressante cette autre piste, pourrais tu développer un peu ton idée ? C'est toujours bien d'avoir plusieurs point de vues sur un problème !

Dernière modification par Maenwe (05-10-2019 08:58:17)

Hors ligne

#9 05-10-2019 14:55:05

Zebulor
Membre
Inscription : 21-10-2018
Messages : 367

Re : Démontrer qu'une application est bijective

Bonjour
@Maewenn:

Maenwe a écrit :

$\frac{(x+y)(x+y+1)}{2}+y=\frac{(x_{1}+y_{1})(x_{1}+y_{1}+1)}{2}+y_{1}$
ce qui se réécrit : $\sum\limits_{k=1}^{x+y}k + y = \sum\limits_{k=1}^{x_{1}+y_{1}}k +y_{1}$ d'où :
$\sum\limits_{k=x_{1}+y_{1}+1}^{x+y}k + y = y_{1}$ (du coup je ne vois pas pourquoi ce serai $\sum\limits_{k=x_{1}+y_{1}+2}^{x+y}k + y = y_{1}$... Je loupe peut-être quelque chose ?).

Non, c'est moi qui me loupe sur ce coup là.. Merci pour ta réponse et je poursuis d'ici quelque temps..

Hors ligne

#10 07-10-2019 10:37:05

Zebulor
Membre
Inscription : 21-10-2018
Messages : 367

Re : Démontrer qu'une application est bijective

rebonjour,
@Maenwe : pour la surjectivité :
[tex]f(x,y)[/tex] est un entier qu'on appelle [tex]n[/tex]. Alors il existe un seul entier [tex]a[/tex] tel que n soit compris entre la somme des [tex]a[/tex] premiers entiers et la somme des [tex]a+1[/tex] premiers entiers, ce qui peut se vérifier en résolvant ces inéquations d'inconnue [tex]a[/tex] :
[tex]\frac {a(a+1)}{2}  \le n[/tex] et [tex]n < \frac{(a+1)(a+2)}{2}[/tex]

Et on trouve [tex]a=E(\frac {\sqrt{8n+1}}{2})[/tex] ... pour [tex]n[/tex] fixé [tex]a[/tex] est unique.
La suite de la démonstration consiste à contruire [tex]x[/tex] et [tex]y[/tex] de sorte que [tex]f(x,y)=n[/tex]
Il se trouve que [tex]x+y=a[/tex] et [tex]y=n-\frac {a(a+1)}{2}[/tex] conviennent, soit  [tex]x=\frac {a(a+3)}{2}-n[/tex] et [tex]y=n-\frac {a(a+1)}{2}[/tex].
On vérifie ensuite qu'ainsi définis [tex]x[/tex] et [tex]y[/tex] sont des entiers naturels, donc appartenant à l'ensemble de départ...

Je me demande si on ne peut pas aussi exploiter les propriétés de la courbe 3D [tex]z=f(x,y)[/tex]...[tex]

PS : j'écrivais dans un post précédent :

Zebulor a écrit :

il existe toujours un entier compris entre la somme des p premiers entiers et la somme des p+1 premiers entiers..

C'est pas tout à fait çà : tout entier est compris entre la somme des [tex]p[/tex] premiers entiers et la somme des [tex]p+1[/tex] premiers entiers, où [tex]p[/tex] est un entier naturel unique.

Dernière modification par Zebulor (07-10-2019 17:33:04)

Hors ligne

#11 07-10-2019 13:17:47

Maenwe
Membre
Inscription : 06-09-2019
Messages : 79

Re : Démontrer qu'une application est bijective

Bonjour,

@Zebulor, super cette démo ! En plus tu as montré l'injectivité par un raisonnement qui est en une analyse-synthèse (tu supposes que ça existe et tu essaye de voir quels sont les propriétés éventuels sur les solutions, et tu obtiens parfois l'unicité) :
Ici il a été montré que si le couple $(x,y)$ est solution de l'équation ($f(x,y)=n$) alors $x+y$ est unique, et donc $\frac{(x+y)(x+y+1)}{2}$ est unique et donc $y$ l'es aussi (car $y = n - \frac{(x+y)(x+y+1)}{2}$), et donc $x$ aussi. Donc c'est une démo bien trouvé :)
En y repensant en utilisant ma piste on peut peut-être aussi montrer l'injectivité en plus de la surjectivité que je vais essayer de développer :

On note $U_{n}=\{(n-t) | t \in [|0,n|] \}$, et on remarque pour $t \in [|0,n-1|]$ on a $f(n-(t+1),t+1) = f(n-t-1,t+1) = 1 + f(n-t,t)$.
On pose $A_{n} = \{ f(n-t,t) | t \in [|0,n|] \}$, et par ce qui précède : $A_{n} = [|f(n,0),f(0,n)|]$, et ce serait quand même bien si $f(0,n) + 1 = f(n+1,0)$, eh bien c'est le cas ! (un petit calcul le montre) donc $A_{n}\cap A_{n+1} = \emptyset $ et $Card(A_{n}) = Card(U_{n})$, ce qui nous donne l'injectivité. Et puisque $f(0,n) \longrightarrow +\infty$ on a : $\cup A_{n} = \mathbb{N} - [|f(0,0)-1, 0 |] = \mathbb{N}$ (car $f(0,0) = 0$). Ce qui nous donne aussi la surjectivité !

C'est peut-être possible mais il faudrait pouvoir repasser dans $\mathbb{N}$ , tu aurais une idée plus précise ?

Dernière modification par Maenwe (07-10-2019 13:19:44)

Hors ligne

#12 07-10-2019 14:29:53

Zebulor
Membre
Inscription : 21-10-2018
Messages : 367

Re : Démontrer qu'une application est bijective

@Maewen : Je pensais avoir du même coup démontré l'injectivité mais je me demande s'il ne manque pas encore quelque chose dans mon raisonnement...
Ton cheminement est plus abstrait mais aussi intéressant..
Sinon on a : [tex]\frac {\partial f(x)}{\partial x}>0[/tex] et [tex]\frac {\partial f(y)}{\partial y}>0[/tex].. est ce qu'on ne peut pas en tirer quelque chose..
[tex]\frac {\partial f(x)}{\partial x}=x+y+\frac {1}{2}[/tex] et [tex]\frac {\partial f(y)}{\partial y}=x+y-\frac {1}{2}[/tex].. une symétrie exploitable?

Dernière modification par Zebulor (07-10-2019 18:32:11)

Hors ligne

#13 07-10-2019 14:44:06

Maenwe
Membre
Inscription : 06-09-2019
Messages : 79

Re : Démontrer qu'une application est bijective

Ce n'est pas si abstrait... Reprend les 3ème poste de ce fil et tu verras apparaitre un schéma récurrent, qui fait de mon raisonnement un simple allongement de l'observation que l'on peut faire (les nombre s'organisent en diagonale dans $\mathbb{R}^{2}$), il s'avère donc que ton raisonnement est plus abstrait que le mien ^^

Non il ne manque rien, enfin si, peut-être faudrait il réorganiser un peu le raisonnement pour qu'il soit un peu plus claire mais sinon pour moi tous tes arguments sont valides.

Je vais y réfléchir voir si ça donne quelque chose cette autre piste...

Dernière modification par Maenwe (07-10-2019 14:44:44)

Hors ligne

#14 08-10-2019 16:31:59

Lorenzo Empreur du sale
Invité

Re : Démontrer qu'une application est bijective

Bonsoir bonsoir,

Remplir le petit tableau que je vous avais suggéré ne donne-t-il pas une piste simple pour trouver la démonstration à faire ? On trouvait :

[tex]\begin{array}{|c||c|c|c|c|c|}
    \hline
    &0&1&2&3&4\\
    \hline
    \hline
    0 & 0 & 2 & 5 & 19 & 14\\
    \hline
    1 & 1 & 4 & 8 & 9\\
    \hline
    2 & 3 & 7 & 12\\
    \hline
    3 & 6 & 11\\
    \hline
    4 & 10\\
    \hline
  \end{array}
[/tex]

Et là, c'est tout ébaubi que l'on constate qu'il suffit de faire "haut droite" pour augmenter de 1, et faire une sorte de "retour à la ligne" si jamais [tex] x = 0[/tex], ce qui amène à considérer la fonction [tex]\begin{array}[t]{rcl}
  \phi:\mathbb N\times\mathbb N & \longrightarrow &\mathbb N\times\mathbb N\\
  (x,y) & \longmapsto & \left|
                        \begin{array}{ll}
                          (x-1,y+1) &\text{si }x\geq1 \\
                          (y+1,0) & \text{si }x=0
                        \end{array}
  \right.
\end{array}
[/tex]

Du coup je rédigerais le truc comme cela :

On pose [tex]\begin{array}[t]{rcl}\phi:\mathbb N\times\mathbb N & \longrightarrow &\mathbb N\times\mathbb N\\
  (x,y) & \longmapsto & \left|
                        \begin{array}{ll}
                          (x-1,y+1) &\text{si }x\geq1 \\
                          (y+1,0) & \text{si }x=0
                        \end{array}
  \right.
\end{array}[/tex] ainsi que [tex]\begin{array}[t]{rcl}
  g:\mathbb N&\longrightarrow&\mathbb N\times\mathbb N\\
  n&\longmapsto &\phi^n((0,0))
\end{array}[/tex].

Alors [tex] f\circ g = Id_{\mathbb N}[/tex] (récurrence assez imméfiate) et [tex] g\circ f = Id_{\mathbb N^2}[/tex] (demande un peu de travail, mais je vais pas tout faire non plus).

Ainsi, la fonction [tex]f[/tex] est bien bijective.

C'est tout pour moi.

#15 08-10-2019 16:34:08

Lorenzo Empreur du sale
Invité

Re : Démontrer qu'une application est bijective

Ouais j'étais bourré quand j'ai rempli la colonne y=3 mais bon ça va vous comprenez l'idée.

#16 08-10-2019 20:21:20

Maenwe
Membre
Inscription : 06-09-2019
Messages : 79

Re : Démontrer qu'une application est bijective

Bonsoir,

C'est exactement l'idée de la preuve au poste #11, sauf que je n'ai pas exhibé de réciproque qui a le mérite d'être plus directe.

Hors ligne

Réponse rapide

Veuillez composer votre message et l'envoyer
Nom (obligatoire)

E-mail (obligatoire)

Message (obligatoire)

Programme anti-spam : Afin de lutter contre le spam, nous vous demandons de bien vouloir répondre à la question suivante. Après inscription sur le site, vous n'aurez plus à répondre à ces questions.

Quel est le résultat de l'opération suivante (donner le résultat en chiffres)?
quarantehuit plus vingt cinq
Système anti-bot

Faites glisser le curseur de gauche à droite pour activer le bouton de confirmation.

Attention : Vous devez activer Javascript dans votre navigateur pour utiliser le système anti-bot.

Pied de page des forums