Une bijection de $\mathbb{N}\times \mathbb{N}$ sur ${\mathbb{N}}^{\ast }$

La stratégie. Montrer qu'une application est bijective, c'est montrer que tout élément de l'arrivée a un et un seul antécédent : l'injectivité est l'unicité, la surjectivité l'existence. Ici, un antécédent de $n$ est une écriture de $n$ comme une puissance de $2$ fois un nombre impair. (L'application $g$ est bien à valeurs dans ${\mathbb{N}}^{\ast }$, puisque $2^p\ge 1$ et $2q+1\ge 1$.)

a) L'injectivité : l'unicité de l'écriture. Soient $(p,q)$ et $(p^{\prime },q^{\prime })$ tels que $2^p(2q+1)=2^{p^{\prime }}(2q^{\prime }+1)$ ; les rôles étant symétriques, on peut supposer $p\le p^{\prime }$. En divisant par $2^p$ : $$2q+1=2^{p^{\prime }-p}(2q^{\prime }+1).$$ Le membre de gauche est impair. Si l'on avait $p^{\prime }>p$, le membre de droite serait pair, puisque $2^{p^{\prime }-p}$ serait un multiple de $2$ : contradiction. Donc $p^{\prime }=p$, l'égalité devient $2q+1=2q^{\prime }+1$, et $q=q^{\prime }$. Ainsi $(p,q)=(p^{\prime },q^{\prime })$ : $g$ est injective.

b) La surjectivité : l'existence de l'écriture. Notons $\mathcal{E}(n)$ l'assertion « $n$ s'écrit $2^{p}m$ avec $p\in \mathbb{N}$ et $m$ impair », et raisonnons par récurrence forte sur $n\ge 1$.

Initialisation. $1=2^0\times 1$, avec $1$ impair : $\mathcal{E}(1)$ est vraie.

Hérédité. Soit $n\ge 1$ tel que $\mathcal{E}(k)$ soit vraie pour tout $k\in \{1,\dots ,n\}$. Si $n+1$ est impair, $n+1=2^0(n+1)$ convient. Si $n+1$ est pair, $n+1=2k$ avec $k$ entier, et $1\le k\le n$ (car $n+1\ge 2$ et $k=\frac{n+1}{2}\le n$). L'hypothèse, appliquée à $k$ — et non à $n$, d'où la nécessité de la forme forte —, fournit $k=2^{p}m$ avec $m$ impair ; alors $n+1=2^{p+1}m$ convient. Donc $\mathcal{E}(n+1)$ est vraie.

Conséquence. Soit $n\in {\mathbb{N}}^{\ast }$, écrit $n=2^{p}m$ avec $m$ impair. Comme $m$ est impair, $m=2q+1$ avec $q=\frac{m-1}{2}\in \mathbb{N}$, et $n=g(p,q)$ : $g$ est surjective. Avec le a), $g$ est bijective.

c) Le calcul de la réciproque. On divise $96$ par $2$ tant que c'est possible : $96=2\times 48=4\times 24=8\times 12=16\times 6=32\times 3$, et $3$ est impair. Donc $96=2^5(2\times 1+1)$ et $g^{-1}(96)=(5,1)$. De même $2026=2\times 1013$ avec $1013$ impair, et $1013=2\times 506+1$ : $g^{-1}(2026)=(1,506)$.

En une phrase : $p$ est le nombre de fois qu'on peut diviser $n$ par $2$, et $q=\frac{m-1}{2}$, où $m=\frac{n}{2^p}$ est le nombre impair qui reste.

d) Composer des bijections. L'application $n\mapsto n-1$ est une bijection de ${\mathbb{N}}^{\ast }$ sur $\mathbb{N}$, de réciproque $k\mapsto k+1$. La composée de deux bijections étant une bijection (cours), $$h:\mathbb{N}\times \mathbb{N}\to \mathbb{N},(p,q)\mapsto 2^p(2q+1)-1$$ est une bijection : $h(0,0)=0$, $h(1,0)=1$, $h(0,1)=2$, $h(2,0)=3$, et ainsi de suite.

Pour trois facteurs, considérons $\Phi :\mathbb{N}\times \mathbb{N}\times \mathbb{N}\to \mathbb{N}\times \mathbb{N}$, $(p,q,r)\mapsto (h(p,q),r)$. Elle est injective : si $(h(p,q),r)=(h(p^{\prime },q^{\prime }),r^{\prime })$, alors $r=r^{\prime }$ et $h(p,q)=h(p^{\prime },q^{\prime })$, donc $(p,q)=(p^{\prime },q^{\prime })$ par injectivité de $h$. Elle est surjective : un couple $(k,r)$ de $\mathbb{N}\times \mathbb{N}$ s'écrit $(h(p,q),r)$, où $(p,q)$ est l'antécédent de $k$ par $h$. Donc $\Phi$ est bijective, et la composée $$h\circ \Phi :(p,q,r)⟼h(h(p,q),r)$$ est une bijection de $\mathbb{N}\times \mathbb{N}\times \mathbb{N}$ sur $\mathbb{N}$. Exemple : $h(1,2)=2\times 5-1=9$, puis $h(9,3)=2^9\times 7-1=3583$ : le triplet $(1,2,3)$ est codé par l'entier $3583$.

Contrôle numérique. Chaque entier de $1$ à $3999$ a bien un antécédent par $g$, et les $512$ triplets de $\{0,\dots ,7{\}}^3$ ont $512$ images distinctes par $h\circ \Phi$.

Ce que l'exercice installe. Montrer qu'une application est bijective, c'est montrer l'existence et l'unicité d'une écriture — ici $n=2^{p}m$ avec $m$ impair, ailleurs l'écriture d'un vecteur dans une base, dont les coordonnées seront de même l'antécédent par une bijection. Et l'on fabrique des bijections compliquées en composant des bijections simples, comme l'informatique range des données à plusieurs indices dans une mémoire à une dimension.