Exercice 49

On note $W_{k} = w_{0} + \cdots + w_{k}$.

1. (a) L'entier $1$ est atteint : $1 = \psi(A)$ avec $A \neq \varnothing$. Les $w_{n}$ étant des entiers au moins égaux à $1$, la partie $A$ est un singleton $\{a\}$ avec $w_{a} = 1$, et $1 \leqslant w_{0} \leqslant w_{a} = 1$. Ensuite, soit $k \in \mathbb{N}$, et $A$ telle que $\psi(A) = W_{k} + 1$. Si l'on avait $w_{k+1} > W_{k} + 1$, tous les $w_{j}$ d'indice $j \geqslant k + 1$ dépasseraient $W_{k} + 1$, donc $A$ serait contenue dans $[\![0\,;k]\!]$ et $\psi(A) \leqslant W_{k}$ : c'est absurde. $$\boxed{w_{0} = 1 \qquad\text{et}\qquad w_{k+1} \leqslant W_{k} + 1}$$

1. (b) Montrons par récurrence sur $k$ que tout entier de $[\![0\,;W_{k}]\!]$ est l'image d'une partie de $[\![0\,;k]\!]$. Pour $k = 0$, $0 = \psi(\varnothing)$ et $1 = \psi(\{0\})$. Supposons le résultat vrai au rang $k$, et soit $N \in [\![W_{k} + 1\,;W_{k+1}]\!]$. Alors $N - w_{k+1} \in [\![W_{k} + 1 - w_{k+1}\,;W_{k}]\!]$, et $W_{k} + 1 - w_{k+1} \geqslant 0$ d'après $(\ast)$ : il existe $A \subset [\![0\,;k]\!]$ telle que $\psi(A) = N - w_{k+1}$, et $N = \psi\big(A \cup \{k + 1\}\big)$. Comme $W_{k} \geqslant k + 1$ tend vers l'infini, tout entier est atteint. $$\boxed{(\ast) \iff \psi \text{ surjective}}$$

2. Supposons $w_{n} = 2^{n}$. Alors $W_{k} = 2^{k+1} - 1$, et $(\ast)$ est vérifiée. Si $A \neq B$ avaient la même image, on retirerait leurs éléments communs, ce qui ne change pas l'égalité, et l'on noterait $m$ le plus grand élément de $A \Delta B$, disons dans $A$. Alors $\psi(A) \geqslant 2^{m}$, tandis que $\psi(B) \leqslant 2^{0} + \cdots + 2^{m-1} = 2^{m} - 1$ : c'est absurde.

Réciproquement, supposons $\psi$ bijective, et montrons $w_{k} = 2^{k}$ par récurrence. On sait que $w_{0} = 1$. Si $w_{j} = 2^{j}$ pour $j \leqslant k$, alors $W_{k} = 2^{k+1} - 1$. Si l'on avait $w_{k+1} \leqslant W_{k}$, la question 1(b) fournirait $A \subset [\![0\,;k]\!]$ telle que $\psi(A) = w_{k+1} = \psi(\{k + 1\})$, avec $A \neq \{k+1\}$, ce qui contredit l'injectivité. Donc $w_{k+1} \geqslant W_{k} + 1$, et $(\ast)$ donne l'égalité $w_{k+1} = 2^{k+1}$. $$\boxed{\psi \text{ bijective} \iff \forall n \in \mathbb{N},\ w_{n} = 2^{n}}$$

3. Pour $w_{n} = 2^{n}$, la bijection $\psi$ traduit l'existence et l'unicité de l'écriture d'un entier en base $2$ : la partie $A$ est l'ensemble des rangs des chiffres égaux à $1$. Par exemple, $13 = 2^{0} + 2^{2} + 2^{3}$ correspond à $A = \{0, 2, 3\}$, et s'écrit $1101$ en base $2$.

La suite $w_{n} = n + 1$ vérifie $(\ast)$, puisque $n + 2 \leqslant \frac{(n+1)(n+2)}{2} + 1$, donc $\psi$ est surjective. Elle n'est pas injective, puisque $3 = w_{2} = w_{0} + w_{1}$. $$\boxed{w_{n} = n + 1 : \ \psi \text{ surjective, non injective}}$$ À retenir : l'écriture binaire n'est pas un simple choix de notation : c'est la seule façon d'écrire tout entier, de manière unique, comme somme de termes distincts d'une suite croissante d'entiers.