Le dernier montant impossible

Dans un pays imaginaire, seules existent des pièces de 5 et de 8 centimes. Certains montants sont faciles à payer, d'autres semblent impossibles. Le but est de déterminer le dernier montant impossible, tout en explorant plusieurs façons de construire et de comprendre un raisonnement par récurrence. On note $\mathbb N=\{0,1,2,\ldots\}$.

I — Cinq chaînes, un seul principe

On dira qu'un entier $n\in\mathbb N$ est atteignable s'il existe $x,y\in\mathbb N$ tels que

$$n=5x+8y.$$

Autrement dit, $n$ est atteignable s'il peut être payé exactement avec des pièces de 5 et de 8 centimes.

1. Explorer les montants entiers de 20 à 32 centimes : rechercher, pour chacun d'eux, une écriture $n=5x+8y$ avec $x,y\in\mathbb N$ lorsqu'une telle écriture semble exister. Relever les montants qui résistent à vos essais et formuler une conjecture sur le plus grand montant impossible.

Pour tout entier $n$, on note désormais $P_n$ la proposition : « $n$ est atteignable ».

2. Montrer que, pour tout $n\in\mathbb N$, $P_n\Rightarrow P_{n+5}$. Expliquer pourquoi $P_{28}$ et cette seule implication ne permettent pas de conclure que tous les entiers supérieurs ou égaux à 28 sont atteignables.

3. Pour $r\in\{0,1,2,3,4\}$ fixé, on considère la proposition

$$A_k^{(r)}:\qquad P_{28+r+5k},\qquad k\in\mathbb N.$$

(a) Démontrer par récurrence sur $k$ que $A_k^{(0)}$ est vraie pour tout $k\in\mathbb N$.

(b) Adapter ce raisonnement aux quatre autres valeurs de $r$.

(c) En déduire que $P_n$ est vraie pour tout entier $n\ge 28$.

Rappel. Pour tout $N\in\mathbb N$, la division euclidienne par 5 permet d'écrire $N=5q+r$, avec $q\in\mathbb N$ et $r\in\{0,1,2,3,4\}$. On pourra appliquer ce résultat à $N=n-28$.

4. Démontrer que 27 n'est pas atteignable. Conclure quant à la conjecture de la question 1.

II — Gagner exactement un centime

La partie précédente a utilisé cinq chaînes de récurrence parallèles. On cherche maintenant une preuve qui parte d'un seul cas initial et passe directement d'un montant au suivant.

5. Trouver deux échanges de pièces qui augmentent le montant total d'exactement 1 centime : l'un en remplaçant uniquement des pièces de 5 par des pièces de 8, l'autre en remplaçant uniquement des pièces de 8 par des pièces de 5. Traduire ces deux échanges par deux égalités numériques.

6. Soit $n$ un entier tel que $n\ge 28$. Supposons $P_n$ vraie. Ainsi, il existe $x,y\in\mathbb N$ tels que $n=5x+8y$.

(a) Montrer que si $x\ge 3$, alors $P_{n+1}$ est vraie.

(b) Montrer que si $x\le 2$ et $y\le 2$, alors $n\le 26$.

(c) En déduire que, si $x\le 2$, on a nécessairement $y\ge 3$, puis établir encore $P_{n+1}$.

(d) Rédiger une démonstration complète par récurrence de la propriété : « pour tout entier $n\ge 28$, $P_n$ est vraie ».

7. Dans la récurrence précédente, $P_n$ fournit l'existence de deux entiers $x$ et $y$, et pas seulement une affirmation vraie. Expliquer comment ces deux « témoins » sont transformés pour construire le rang suivant.

III — Quand le rang précédent ne suffit pas

Principe de récurrence forte. Pour démontrer qu'une propriété $P_n$ est vraie pour tout entier $n\ge n_0$, on vérifie d'abord les cas initiaux nécessaires. L'hérédité consiste ensuite à établir que, pour tout entier $n$ à partir du dernier rang initial, si toutes les propriétés $P_{n_0},P_{n_0+1},\ldots,P_n$ sont vraies, alors $P_{n+1}$ est vraie.

8. Retrouver le résultat « tout entier $n\ge 28$ est atteignable » par récurrence forte.

(a) Vérifier explicitement $P_{28},P_{29},P_{30},P_{31}$ et $P_{32}$.

(b) Soit $n$ un entier tel que $n\ge 32$. Supposons vraies toutes les propriétés $P_{28},P_{29},\ldots,P_n$. Montrer que $P_{n+1}$ est vraie en utilisant un montant déjà connu et une seule pièce supplémentaire.

(c) Conclure.

9. Pourquoi l'hypothèse ordinaire « $P_n$ est vraie » ne suffit-elle pas, à elle seule, pour reproduire exactement la preuve de la question 8 ?

Pour $n\ge 32$, on définit

$$Q_n:\qquad P_{28},P_{29},\ldots\text{ et }P_n\text{ sont toutes vraies}.$$

10. Montrer que $Q_{32}$ est vraie puis que, pour tout $n\ge 32$, $Q_n\Rightarrow Q_{n+1}$. En déduire qu'ici la récurrence forte se ramène à une récurrence ordinaire sur une propriété plus riche.

IV — Changer de monnaie

Dans un second pays, seules existent des pièces de 6 et de 11 centimes. On note $R_n$ la proposition : « $n$ peut être payé avec des pièces de 6 et de 11 centimes ».

11. Montrer que les six montants 50, 51, 52, 53, 54, 55 sont atteignables. Ces calculs suggèrent-ils un candidat naturel pour le dernier montant impossible ?

12. Trouver deux échanges de pièces de 6 et de 11 centimes qui augmentent le total d'exactement 1 centime. En déduire par récurrence ordinaire que $R_n$ est vraie pour tout $n\ge 50$, à partir de $R_{50}$.

13. Redémontrer ce résultat par récurrence forte, à partir des six cas de la question 11 et du fait qu'ajouter une pièce de 6 conserve l'atteignabilité.

14. Démontrer que 49 n'est pas atteignable. Quel est donc le dernier montant impossible avec des pièces de 6 et de 11 centimes ?

15. Comparer les deux derniers montants impossibles aux valeurs des pièces et conjecturer une formule pour deux entiers $a,b\ge 2$ n'ayant aucun facteur commun supérieur à 1. Aucune preuve générale n'est demandée.