Le dernier montant impossible

I — Cinq chaînes, un seul principe

On cherche les écritures $n=5x+8y$ avec $x,y\in\mathbb N$. Entre 20 et 32, une recherche systématique donne par exemple :

$$\begin{aligned} 20&=4\times5, & 21&=5+2\times8,\\ 22&:\ \text{impossible}, & 23&=3\times5+8,\\ 24&=3\times8, & 25&=5\times5,\\ 26&=2\times5+2\times8, & 27&:\ \text{impossible},\\ 28&=4\times5+8, & 29&=5+3\times8,\\ 30&=6\times5, & 31&=3\times5+2\times8,\\ 32&=4\times8.&& \end{aligned}$$

Pour 22 et 27, un balayage des quelques valeurs possibles de $y$ ne fournit aucune écriture. La suite $28,29,30,31,32$ est constituée de cinq montants consécutifs atteignables. À ce stade, on conjecture donc que 27 est le plus grand montant impossible ; la question 4 en donnera une preuve rigoureuse.

Soit $n\in\mathbb N$. Supposons $P_n$ vraie. Il existe donc $x,y\in\mathbb N$ tels que

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

Alors

$$n+5=5(x+1)+8y,$$

et $x+1,y\in\mathbb N$. Donc $P_{n+5}$ est vraie. Ainsi

$$P_n\Rightarrow P_{n+5}.$$

En revanche, en partant seulement de $P_{28}$, on obtient

$$P_{33},P_{38},P_{43},\ldots$$

mais pas $P_{29},P_{30},P_{31}$ ou $P_{32}$. Une hérédité de pas 5 ne parcourt donc qu'une seule des cinq chaînes possibles ; il faut cinq points de départ pour couvrir tous les entiers à partir de 28.

(a) Pour $r=0$, posons

$$A_k^{(0)}: P_{28+5k}.$$

Initialisation. Pour $k=0$, $28=4\times5+8$, donc $P_{28}$ est vraie. Ainsi $A_0^{(0)}$ est vraie.

Hérédité. Soit $k\in\mathbb N$. Supposons $A_k^{(0)}$ vraie, c'est-à-dire $P_{28+5k}$ vraie. D'après la question 2,

$$P_{28+5k}\Rightarrow P_{28+5k+5}=P_{28+5(k+1)}.$$

Donc $A_{k+1}^{(0)}$ est vraie.

Conclusion. Par récurrence, $A_k^{(0)}$ est vraie pour tout $k\in\mathbb N$.

(b) Fixons $r\in\{1,2,3,4\}$. Les initialisations sont respectivement

$$29=5+3\times8,\qquad 30=6\times5,\qquad 31=3\times5+2\times8,\qquad 32=4\times8.$$

Soit $k\in\mathbb N$. Supposons $P_{28+r+5k}$ vraie. D'après la question 2,

$$P_{28+r+5k}\Rightarrow P_{28+r+5k+5}=P_{28+r+5(k+1)}.$$

L'hérédité est donc établie pour cette valeur arbitraire de $r$. Par récurrence, pour tout $k\in\mathbb N$,

$$P_{28+5k},\ P_{29+5k},\ P_{30+5k},\ P_{31+5k},\ P_{32+5k}$$

sont vraies.

(c) Soit $n\ge 28$. Effectuons la division euclidienne de $n-28$ par 5 : il existe $k\in\mathbb N$ et $r\in\{0,1,2,3,4\}$ tels que

$$n-28=5k+r.$$

Ainsi

$$n=28+r+5k.$$

La proposition correspondante a été démontrée en (a) ou (b), donc $P_n$ est vraie. Finalement,

$$\forall n\in\mathbb N,\qquad n\ge28\Rightarrow P_n.$$

Supposons, pour obtenir une contradiction, que 27 soit atteignable. Il existerait $x,y\in\mathbb N$ tels que

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

Comme $8y\le27$, on a nécessairement $y\in\{0,1,2,3\}$. On examine ces quatre cas :

$$27-8y\in\{27,19,11,3\}.$$

Aucun de ces quatre entiers n'est un multiple de 5. Il est donc impossible d'avoir $5x=27-8y$ avec $x\in\mathbb N$.

Ainsi 27 n'est pas atteignable. Comme tous les entiers $n\ge28$ le sont d'après la question 3, on a bien

$$\boxed{27\text{ est le dernier montant impossible}.}$$

II — Gagner exactement un centime

On cherche d'abord à remplacer des pièces de 5 par des pièces de 8 tout en augmentant le total de 1. Or

$$2\times8=16=15+1=3\times5+1.$$

Donc remplacer trois pièces de 5 par deux pièces de 8 augmente le total de 1 centime.

Dans l'autre sens,

$$5\times5=25=24+1=3\times8+1.$$

Donc remplacer trois pièces de 8 par cinq pièces de 5 augmente également le total de 1 centime.

Les deux égalités utiles sont donc

$$2\times8=3\times5+1 \qquad\text{et}\qquad 5\times5=3\times8+1.$$

Soit $n$ un entier tel que $n\ge28$. Supposons $P_n$ vraie. Il existe donc $x,y\in\mathbb N$ tels que

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

(a) Si $x\ge3$, alors $x-3\in\mathbb N$ et $y+2\in\mathbb N$. De plus,

$$5(x-3)+8(y+2)=5x+8y-15+16=n+1.$$

Donc $P_{n+1}$ est vraie.

(b) Si $x\le2$ et $y\le2$, alors

$$n=5x+8y\le5\times2+8\times2=26.$$

(c) Or on sait que $n\ge28$. Le cas $x\le2$ et $y\le2$ est donc impossible. Par conséquent, si $x\le2$, il faut nécessairement avoir $y\ge3$.

Dans ce cas, $x+5\in\mathbb N$ et $y-3\in\mathbb N$, et

$$5(x+5)+8(y-3)=5x+8y+25-24=n+1.$$

Donc $P_{n+1}$ est encore vraie.

Ainsi, quelle que soit la représentation $n=5x+8y$, l'une des deux transformations permet d'obtenir une représentation de $n+1$.

(d) On rédige maintenant la récurrence complète.

Propriété. Pour $n\ge28$, $P_n$ signifie : « il existe $x,y\in\mathbb N$ tels que $n=5x+8y$ ».

Initialisation. On a

$$28=4\times5+1\times8,$$

Donc $P_{28}$ est vraie.

Hérédité. Soit $n$ un entier tel que $n\ge28$. Supposons $P_n$ vraie. Il existe $x,y\in\mathbb N$ tels que $n=5x+8y$. Si $x\ge3$, la question (a) donne $P_{n+1}$. Si $x\le2$, alors la question (b), combinée à $n\ge28$, impose $y\ge3$, et la question (c) donne encore $P_{n+1}$. Dans tous les cas, $P_n\Rightarrow P_{n+1}$.

Conclusion. Par récurrence,

$$P_n\text{ est vraie pour tout entier }n\ge28.$$

L'hypothèse $P_n$ affirme l'existence d'une représentation

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

Les entiers $x$ et $y$ sont donc des témoins de l'atteignabilité de $n$.

Si $x\ge3$, on transforme le couple $(x,y)$ en

$$(x-3,y+2),$$

ce qui augmente la valeur totale de 1. Si $x\le2$, alors la taille de $n$ force $y\ge3$, et on transforme le couple en

$$(x+5,y-3).$$

Dans les deux cas, l'hypothèse de récurrence fournit des objets concrets que l'on modifie pour fabriquer ceux du rang suivant. C'est l'utilisation effective de l'hypothèse qui constitue le cœur de l'hérédité.

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

(a) On a déjà les cinq représentations

$$28=4\times5+8,\qquad 29=5+3\times8,$$ $$30=6\times5,\qquad 31=3\times5+2\times8,$$ $$32=4\times8.$$

Donc $P_{28},P_{29},P_{30},P_{31},P_{32}$ sont vraies.

(b) Soit $n$ un entier tel que $n\ge32$. Supposons vraies toutes les propriétés

$$P_{28},P_{29},\ldots,P_n.$$

Comme $n\ge32$, on a

$$n-4\ge28.$$

De plus $n-4\le n$, donc $P_{n-4}$ fait partie des propriétés supposées vraies. Il existe donc $x,y\in\mathbb N$ tels que

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

En ajoutant une pièce de 5,

$$n+1=(n-4)+5=5(x+1)+8y.$$

Ainsi $P_{n+1}$ est vraie.

(c) Les cinq cas initiaux sont vrais et l'hérédité forte est établie. Par récurrence forte,

$$P_n\text{ est vraie pour tout entier }n\ge28.$$

La preuve de la question 8 ne se sert pas de $P_n$ pour construire $P_{n+1}$. Elle se sert de $P_{n-4}$.

Or l'hypothèse ordinaire « $P_n$ est vraie » ne contient aucune information sur $P_{n-4}$. La récurrence forte fournit précisément cette information, puisqu'elle suppose simultanément vraies toutes les propriétés depuis le premier rang considéré jusqu'au rang $n$.

Cela ne signifie pas que la récurrence ordinaire est moins puissante : on peut enrichir la propriété sur laquelle on effectue la récurrence, ce qui est l'objet de la question suivante.

Par définition,

$$Q_{32}: P_{28},P_{29},P_{30},P_{31},P_{32}\text{ sont toutes vraies}.$$

La question 8(a) montre donc que $Q_{32}$ est vraie.

Soit maintenant $n$ un entier tel que $n\ge32$. Supposons $Q_n$ vraie. On sait alors en particulier que $P_{n-4}$ est vraie, puisque $28\le n-4\le n$. Comme dans la question 8, on ajoute une pièce de 5 et on obtient $P_{n+1}$.

L'hypothèse $Q_n$ contenait déjà $P_{28},\ldots,P_n$ ; en ajoutant $P_{n+1}$, on obtient donc $Q_{n+1}$. Ainsi

$$Q_n\Rightarrow Q_{n+1}.$$

Par récurrence ordinaire, $Q_n$ est vraie pour tout $n\ge32$. Cela entraîne en particulier $P_n$ pour tout $n\ge28$.

La récurrence forte de la question 8 peut donc être vue ici comme une récurrence ordinaire sur la propriété renforcée

$$Q_n=P_{28}\land P_{29}\land\cdots\land P_n.$$

IDÉEUne difficulté fréquente en récurrence vient d'une hypothèse trop pauvre. Lorsqu'elle ne contient pas assez d'information pour construire le rang suivant, une stratégie générale consiste à renforcer la propriété que l'on veut transmettre.

IV — Changer de monnaie

On vérifie :

$$50=6+4\times11,\qquad 51=3\times6+3\times11,$$ $$52=5\times6+2\times11,\qquad 53=7\times6+11,$$ $$54=9\times6,\qquad 55=5\times11.$$

On dispose donc de six montants consécutifs atteignables à partir de 50. Cela suggère fortement que 49 pourrait être le dernier montant impossible.

Deux échanges augmentant le total de 1 sont particulièrement simples :

$$2\times6=12=11+1,$$

donc remplacer une pièce de 11 par deux pièces de 6 fait gagner 1 centime ; et

$$5\times11=55=54+1=9\times6+1,$$

donc remplacer neuf pièces de 6 par cinq pièces de 11 fait également gagner 1 centime.

Montrons par récurrence que $R_n$ est vraie pour tout $n\ge50$.

Initialisation. $50=6+4\times11$, donc $R_{50}$ est vraie.

Hérédité. Soit $n$ un entier tel que $n\ge50$. Supposons $R_n$ vraie. Il existe $x,y\in\mathbb N$ tels que

$$n=6x+11y.$$

Si $y\ge1$, on remplace une pièce de 11 par deux pièces de 6 :

$$n+1=6(x+2)+11(y-1),$$

donc $R_{n+1}$ est vraie.

Si $y=0$, alors $n=6x\ge50$. Comme $x$ est entier, on a nécessairement $x\ge9$. On peut alors remplacer neuf pièces de 6 par cinq pièces de 11 :

$$n+1=6(x-9)+11(y+5)=6(x-9)+55.$$

Les coefficients sont non négatifs, donc $R_{n+1}$ est encore vraie.

Dans tous les cas, $R_n\Rightarrow R_{n+1}$. Par récurrence,

$$R_n\text{ est vraie pour tout entier }n\ge50.$$

Les six cas initiaux $R_{50},R_{51},\ldots,R_{55}$ sont vrais d'après la question 11.

Soit $n$ un entier tel que $n\ge55$. Supposons vraies toutes les propriétés

$$R_{50},R_{51},\ldots,R_n.$$

Alors

$$n-5\ge50$$

et $n-5\le n$, donc $R_{n-5}$ est vraie. Il existe $x,y\in\mathbb N$ tels que

$$n-5=6x+11y.$$

En ajoutant une pièce de 6,

$$n+1=(n-5)+6=6(x+1)+11y.$$

Donc $R_{n+1}$ est vraie.

Par récurrence forte,

$$R_n\text{ est vraie pour tout entier }n\ge50.$$

Cette preuve demande six cas initiaux mais son hérédité est très courte. La preuve ordinaire de la question 12 ne demande qu'un seul cas initial, mais son hérédité exige une analyse des représentations disponibles.

Supposons que 49 soit atteignable :

$$49=6x+11y,$$

avec $x,y\in\mathbb N$. Comme $11y\le49$, on a $y\in\{0,1,2,3,4\}$. Alors

$$49-11y\in\{49,38,27,16,5\}.$$

Aucun de ces nombres n'est divisible par 6. Il n'existe donc pas de $x\in\mathbb N$ satisfaisant l'égalité.

Ainsi 49 n'est pas atteignable, tandis que tout entier $n\ge50$ l'est. Donc

$$\boxed{49\text{ est le dernier montant impossible}.}$$

Pour les pièces de 5 et 8, le dernier montant impossible vaut

$$27=5\times8-5-8.$$

Pour les pièces de 6 et 11,

$$49=6\times11-6-11.$$

On est donc naturellement conduit à conjecturer que, pour deux entiers $a,b\ge2$ sans facteur commun autre que 1, le dernier montant impossible est

$$ab-a-b.$$

Cette conjecture est vraie : lorsque $a$ et $b$ n'ont aucun facteur commun supérieur à 1 (on dit qu'ils sont premiers entre eux), le plus grand entier non représentable sous la forme $ax+by$ avec $x,y\in\mathbb N$ vaut $ab-a-b$. C'est le cas à deux valeurs du problème des pièces de Frobenius.

Sources

[SOURCE] J. L. Ramírez Alfonsín et M. Skałba — Primes in numerical semigroups, Comptes Rendus Mathématique 358 (2020), publié en 2021. Lien direct