Exercice 47

1. Calculons $S_{m}$ lorsque $r = 2$. En multipliant par $2$, on décale les termes : $$2S_{m} = 2 + 4 + \dots + 2^{m} + 2^{m+1} = (S_{m} - 1) + 2^{m+1},$$ d'où $S_{m} = 2^{m+1} - 1$. Il suffit donc de donner une pièce de valeur $2^{m+1}$ et de recevoir une pièce de valeur $1$ : avec $M = m + 1$, on prend $k_{0} = -1$, $k_{m+1} = 1$ et tous les autres $k_{i}$ nuls. $$\boxed{S_{m} = 2^{m+1} - 1 \text{ se règle avec deux pièces.}}$$ Par exemple, $15 = 1 + 2 + 4 + 8$ se règle avec une pièce de $16$, contre laquelle on reçoit une pièce de $1$. Pour $m \geqslant 2$, c'est strictement mieux que les $m + 1$ pièces du paiement direct.

2. (a) On a $S_{0} = 1$. Si $k_{0} + k_{1}\,r + \dots + k_{M}\,r^{M} = 1$, les $k_{i}$ ne sont pas tous nuls, sinon la somme serait nulle. L'un d'eux est donc un entier non nul, de valeur absolue au moins égale à $1$, et $|k_{0}| + \dots + |k_{M}| \geqslant 1$. $$\boxed{P(0) \text{ est vraie.}}$$

2. (b) Si $M = 0$, on complète la liste par un coefficient $k_{1} = 0$ : ni la somme réglée ni la somme des valeurs absolues ne changent. On peut donc supposer $M \geqslant 1$. Comme $m \geqslant 1$, on a $S_{m} - 1 = r + r^{2} + \dots + r^{m} = r\,S_{m-1}$, d'où $$k_{0} - 1 = (S_{m} - 1) - \big(k_{1}\,r + \dots + k_{M}\,r^{M}\big) = r\,\Big(S_{m-1} - \big(k_{1} + k_{2}\,r + \dots + k_{M}\,r^{M-1}\big)\Big).$$

2. (c) L'égalité obtenue pour $t$ s'écrit aussi $$\boxed{(k_{1} + t) + k_{2}\,r + \dots + k_{M}\,r^{M-1} = S_{m-1}.}$$ La liste $(k_{1} + t, k_{2}, \dots, k_{M})$, de longueur $M$, permet donc de régler $S_{m-1}$, et l'hypothèse $P(m-1)$, qui porte sur toutes les listes d'entiers relatifs, s'applique à elle : $$|k_{1} + t| + |k_{2}| + \dots + |k_{M}| \geqslant m.$$ On rappelle que $|a + b| \leqslant |a| + |b|$ pour tous réels $a$ et $b$, puisque $a + b$ et $-(a + b)$ sont tous deux majorés par $|a| + |b|$. Ainsi $|k_{1} + t| \leqslant |k_{1}| + |t|$, et $$\boxed{|k_{1}| + |k_{2}| + \dots + |k_{M}| \geqslant m - |t|.}$$

2. (d) Notons $W = |k_{0}| + |k_{1}| + \dots + |k_{M}|$. La question précédente donne $W \geqslant |k_{0}| + m - |t|$.

• Si $t = 0$, alors $k_{0} = 1$ et $W \geqslant 1 + m$.

• Si $t \neq 0$, alors $|t| \geqslant 1$. L'inégalité rappelée en (c) donne $r\,|t| = |tr| \leqslant |1 + tr| + |{-1}|$, c'est-à-dire $|k_{0}| \geqslant r\,|t| - 1$. Par conséquent, $$W \geqslant r\,|t| - 1 + m - |t| = m + (r - 1)\,|t| - 1 \geqslant m + (r - 1) - 1 = m + r - 2 \geqslant m + 1,$$ la dernière inégalité venant de $r \geqslant 3$.

Dans les deux cas, $W \geqslant m + 1$ : l'assertion $P(m)$ est vraie. Le principe de récurrence (théorème 3 du cours) montre alors que $P(m)$ est vraie pour tout $m \in \mathbb{N}$. Comme le paiement direct, avec $k_{0} = k_{1} = \dots = k_{m} = 1$, utilise exactement $m + 1$ pièces, la minoration est atteinte. $$\boxed{\text{Pour } r \geqslant 3, \text{ il faut au minimum } m + 1 \text{ pièces pour régler } S_{m} = 1 + r + \dots + r^{m}.}$$ Autrement dit, rendre la monnaie ne permet jamais d'économiser une pièce sur cette somme. Ce résultat a été contrôlé par ordinateur pour $r \in \{3, 4, 5\}$ et $m \leqslant 3$, sur toutes les listes de coefficients compris entre $-3$ et $3$.

3. L'hypothèse $r \geqslant 3$ n'a servi qu'à la toute dernière inégalité, $m + r - 2 \geqslant m + 1$, dans le cas $t \neq 0$. Pour $r = 2$, ce cas ne fournit que $W \geqslant m$, et la récurrence ne se propage plus. Ce n'est pas une faiblesse de la démonstration : la question 1 montre que $P(m)$ est fausse pour $r = 2$ dès que $m \geqslant 2$. Le paiement de la question 1 correspond précisément au cas $t \neq 0$, puisque $k_{0} = -1 = 1 + (-1) \times 2$. $$\boxed{\text{L'hypothèse } r \geqslant 3 \text{ est indispensable.}}$$ À retenir : l'assertion $P(m)$ porte sur toutes les listes de coefficients, de toutes les longueurs, et c'est indispensable : l'hérédité applique l'hypothèse de récurrence à une liste nouvelle, $(k_{1} + t, k_{2}, \dots, k_{M})$, et non à la liste de départ. Une récurrence dont l'hypothèse porterait sur une liste fixée ne pourrait pas aboutir. On retrouve la leçon des exercices 19 et 24 : l'hypothèse de récurrence doit être assez riche pour s'appliquer aux objets que fabrique l'hérédité. En base $2$, l'égalité $1 + 2 + \dots + 2^{m} = 2^{m+1} - 1$ sert au contraire en informatique pour accélérer certaines multiplications, en remplaçant une longue suite de chiffres $1$ par une soustraction.