Exercice · Mathématiques · Sciences Mathématiques

Une bijection de ℕ×ℕ sur ℕ

Matière
Mathématiques
Niveau
1ère Bac
Filière
Sciences Mathématiques
Session
Semestre 1
Exercice 1

Une bijection de ℕ×ℕ sur ℕ

Difficile

On considère l’application \(f:\mathbb{N}\times\mathbb{N}\to\mathbb{N}\), \((p;q)\mapsto2^{p}(2q+1)-1\).

1) Calculer \(f(0;0)\), \(f(3;2)\) et \(f(1;5)\).

2) Montrer que \(f\) est injective. (Supposer \(p\le p^{\prime}\) et diviser par \(2^{p}\).)

3) Montrer que \(f\) est surjective. (Pour \(n\in\mathbb{N}\), considérer le plus grand entier \(p\) tel que \(2^{p}\) divise \(n+1\).)

4) Déterminer \(f^{-1}(2026)\) et \(f^{-1}(95)\).

Afficher la correctionMasquer la correction

1) Calculs.

\(f(0;0)=1-1=0\) ; \(f(3;2)=8\times5-1=39\) ; \(f(1;5)=2\times11-1=21\).

2) Injectivité.

Supposons \(f(p;q)=f(p^{\prime};q^{\prime})\), soit \(2^{p}(2q+1)=2^{p^{\prime}}(2q^{\prime}+1)\), avec par exemple \(p\le p^{\prime}\). En divisant par \(2^{p}\) : \(2q+1=2^{p^{\prime}-p}(2q^{\prime}+1)\).

Le premier membre est impair ; si \(p^{\prime}-p\ge1\), le second serait pair : contradiction. Donc \(p^{\prime}=p\), puis \(2q+1=2q^{\prime}+1\) et \(q=q^{\prime}\). \(f\) est injective.

3) Surjectivité.

Soit \(n\in\mathbb{N}\) ; on a \(n+1\ge1\). Les entiers \(p\) tels que \(2^{p}\) divise \(n+1\) vérifient \(2^{p}\le n+1\) : ils sont en nombre fini et \(p=0\) en fait partie. Soit \(p\) le plus grand d’entre eux et \(m=\frac{n+1}{2^{p}}\).

Si \(m\) était pair, \(2^{p+1}\) diviserait \(n+1\), ce qui contredit le choix de \(p\). Donc \(m\) est impair : \(m=2q+1\) avec \(q\in\mathbb{N}\), et \(n=2^{p}(2q+1)-1=f(p;q)\). \(f\) est surjective, donc bijective.

4) Antécédents.

\(2026+1=2027\) est impair : \(p=0\) et \(2q+1=2027\), donc \(f^{-1}(2026)=(0;1013)\).

\(95+1=96=2^{5}\times3\) : \(p=5\) et \(2q+1=3\), donc \(f^{-1}(95)=(5;1)\).

Retour à la leçon « Ensembles et applications »