Exercice 48

1. On calcule les sommes, en lisant les chiffres de droite à gauche à partir de l'indice $0$ : $$(11010)_{-2} = (-2)^{4} + (-2)^{3} + (-2)^{1} = 16 - 8 - 2 = 6, \qquad (1111)_{-2} = -8 + 4 - 2 + 1 = -5.$$ De même, $-1 = -2 + 1$, $2 = 4 - 2$ et $3 = 4 - 2 + 1$. $$\boxed{-1 = (11)_{-2}, \qquad 2 = (110)_{-2}, \qquad 3 = (111)_{-2}}$$

2. Les termes d'indice $k < m$ sont nuls, et l'on factorise par $(-2)^{m}$ : $$\sum_{k=0}^{N} (\varepsilon_{k} - \eta_{k})\,(-2)^{k} = (-2)^{m} \Big( (\varepsilon_{m} - \eta_{m}) - 2 \sum_{k=m+1}^{N} (\varepsilon_{k} - \eta_{k})\,(-2)^{k-m-1} \Big).$$ Le facteur entre parenthèses est la somme de $\varepsilon_{m} - \eta_{m} = \pm 1$ et d'un entier pair : il est impair, donc non nul. $$\boxed{\sum_{k=0}^{N} (\varepsilon_{k} - \eta_{k})\,(-2)^{k} = (-2)^{m} \times (\text{entier impair}) \neq 0}$$ Si $p$ avait deux écritures distinctes, on les compléterait par des chiffres nuls à gauche pour qu'elles aient la même longueur $N + 1$ ; la différence des deux sommes serait nulle, ce qui contredit ce qui précède. L'écriture en base $-2$, si elle existe, est donc unique.

3. Comme $p$ et $\varepsilon$ ont même parité, $\varepsilon - p$ est pair et $p'$ est un entier ; de plus, $\varepsilon - 2p' = p$. Par l'inégalité triangulaire, $$|p'| \leqslant \frac{|\varepsilon| + |p|}{2} \leqslant \frac{1 + |p|}{2},$$ qui est strictement inférieur à $|p|$ dès que $|p| > 1$.

Montrons par récurrence forte sur $m \geqslant 1$ que tout entier $p$ tel que $|p| \leqslant m$ admet une écriture en base $-2$. Pour $m = 1$, on a $0 = (0)_{-2}$, $1 = (1)_{-2}$ et $-1 = (11)_{-2}$. Supposons le résultat vrai jusqu'au rang $m$, et soit $p$ tel que $|p| = m + 1 \geqslant 2$. Alors $|p'| \leqslant m$, et $p'$ admet une écriture $(\varepsilon'_{0}, \dots, \varepsilon'_{N})$. La translation d'indice $j = k + 1$ donne $$p = \varepsilon + (-2) \sum_{k=0}^{N} \varepsilon'_{k}\, (-2)^{k} = \varepsilon + \sum_{j=1}^{N+1} \varepsilon'_{j-1}\, (-2)^{j},$$ de sorte que $(\varepsilon, \varepsilon'_{0}, \dots, \varepsilon'_{N})$ est une écriture de $p$. $$\boxed{\text{tout entier relatif admet une unique écriture en base } -2}$$ Pour $p = 6$, on calcule successivement les couples $(p, \varepsilon)$ suivants : $$(6, 0), \quad (-3, 1), \quad (2, 0), \quad (-1, 1), \quad (1, 1), \quad \text{puis } p' = 0.$$ Les chiffres $\varepsilon$ obtenus, lus de droite à gauche, redonnent $6 = (11010)_{-2}$. ✓

Piège : l'inégalité $|p'| < |p|$ est fausse pour $p = -1$, qui donne $p' = 1$. C'est pourquoi l'initialisation doit traiter $-1$ en plus de $0$ et $1$ : une récurrence initialisée au seul entier $0$ ne démontrerait rien.

4. (a) Les termes $(-2)^{k}$ d'indice pair valent $4^{k/2} > 0$, et ceux d'indice impair $k = 2j + 1$ valent $-2 \times 4^{j} < 0$. La somme est donc maximale lorsque l'on garde tous les termes d'indice pair et aucun terme d'indice impair, et minimale dans le cas contraire. Avec $N = 2M + 1$, les indices pairs sont les $2j$ et les indices impairs les $2j + 1$, pour $j \in [\![0\,;M]\!]$ ; on obtient deux sommes géométriques de raison $4$. $$\boxed{\max = \sum_{j=0}^{M} 4^{j} = \frac{4^{M+1} - 1}{3} = a_{M}, \qquad \min = -2\sum_{j=0}^{M} 4^{j} = -2a_{M}}$$

4. (b) L'application qui associe à $(\varepsilon_{0}, \dots, \varepsilon_{N}) \in \{0, 1\}^{N+1}$ la somme $\sum_{k=0}^{N} \varepsilon_{k} (-2)^{k}$ est injective d'après la question 2, et elle est à valeurs dans $[\![-2a_{M}\,;a_{M}]\!]$ d'après la question 4(a). Or l'ensemble de départ a $2^{N+1} = 4^{M+1}$ éléments, d'après le lemme 6 du chapitre 2 sur les produits cartésiens, appliqué de proche en proche, et l'ensemble d'arrivée en a $$a_{M} + 2a_{M} + 1 = 3a_{M} + 1 = 4^{M+1}.$$ D'après le théorème 2 du chapitre 2, une injection entre deux ensembles finis de même cardinal est bijective : tout entier de $[\![-2a_{M}\,;a_{M}]\!]$ admet une écriture à $2M + 2$ chiffres.

Pour conclure, la formule du binôme donne $4^{M+1} = (1 + 3)^{M+1} \geqslant 1 + 3(M + 1)$, en ne gardant que les deux premiers termes, donc $a_{M} \geqslant M + 1$. Pour $p \in \mathbb{Z}$, on choisit $M = |p|$ : alors $-2a_{M} \leqslant -|p| \leqslant p \leqslant |p| \leqslant a_{M}$, et $p$ admet une écriture en base $-2$. $$\boxed{\text{les écritures à } 2M + 2 \text{ chiffres décrivent exactement } [\![-2a_{M}\,;a_{M}]\!]}$$ Pour $M = 1$, les seize écritures à quatre chiffres décrivent ainsi les seize entiers de $[\![-10\,;5]\!]$.

À retenir : l'algorithme de la question 3 est une division par $-2$ avec un reste égal à $0$ ou à $1$, comme l'écriture en base $2$ procède par divisions successives par $2$. Mais là où la base $2$ ne décrit que les entiers naturels, comme à l'exercice 49, et demande un signe pour les autres, la base $-2$ décrit tous les entiers relatifs. La question 4 montre une idée qui resservira souvent : pour une application entre deux ensembles finis de même cardinal, l'unicité entraîne l'existence.