Une bijection de ℕ×ℕ sur ℕ
DifficileOn 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)\).