Raisonnement par invariant

On étudie un processus : on part d'un état initial $x_0$ et, à chaque étape, on remplace l'état courant $x$ par un état $x'$ que la règle autorise, ce que l'on note $x \to x'$. Une quantité $f$, définie sur tous les états, est un invariant si $f(x') = f(x)$ pour toute étape $x \to x'$ partant de n'importe quel état, et pas seulement de l'état initial. Lorsque la règle est une transformation $T$, qui associe à chaque état un unique état suivant, cela s'écrit $f \circ T = f$. Plus généralement, une propriété est invariante si, vraie dans un état, elle reste vraie après toute étape (par exemple « tous les nombres écrits sont des entiers naturels »).

Un état $y$ est accessible depuis $x_0$ s'il existe un entier naturel $N$ et des états $x_1, \dots, x_N$ tels que $x_0 \to x_1 \to \cdots \to x_N$ et $x_N = y$. Il est inaccessible dans le cas contraire, ce qui s'écrit en niant l'existence : pour tout $N$ et toute suite de $N$ étapes partant de $x_0$, l'état $x_N$ est différent de $y$. Prouver une accessibilité, c'est exhiber des étapes ; prouver une inaccessibilité, c'est donner un argument valable pour toutes les suites d'étapes à la fois.

Si $f$ est un invariant et si $x_0 \to x_1 \to \cdots \to x_N$, alors $f(x_k) = f(x_0)$ pour tout $k \in \llbracket 0, N \rrbracket$ : on le démontre par récurrence sur $k$, et l'hérédité n'est autre que la définition de l'invariant. Par conséquent, si $y$ est accessible depuis $x_0$, alors $f(y) = f(x_0)$. Par contraposée, si $f(y) \neq f(x_0)$, l'état $y$ est inaccessible. La réciproque est fausse en général : l'égalité $f(y) = f(x_0)$ est une condition nécessaire d'accessibilité, qui n'est pas suffisante en général ; pour prouver qu'un état est accessible, on exhibe des étapes qui y mènent.

Soit $m \ge 2$ un entier. Pour des entiers $p$ et $q$, on écrit $p \equiv q \ [m]$ lorsque $m$ divise $p - q$, c'est-à-dire lorsque $p$ et $q$ ont le même reste dans la division euclidienne par $m$ ; ce reste est compris entre $0$ et $m - 1$, même pour un entier négatif. Une quantité entière $f$ a un reste invariant modulo $m$ si, pour toute étape $x \to x'$, la variation $f(x') - f(x)$ est un multiple de $m$ ; pour $m = 2$, on parle d'invariant de parité. La quantité $f$ peut alors changer à chaque étape : seul son reste est conservé, et c'est la seule information que l'on a le droit d'utiliser ensuite.

Un état est la situation complète entre deux étapes (les nombres écrits, le contenu des tas) ; une étape est une application de la règle. Invariant et quantité conservée sont synonymes : même valeur avant et après toute étape. « Une étape quelconque » annonce que l'on démontre un énoncé pour toutes les étapes, et non sur un exemple. « Décroît strictement » s'oppose à « décroît », qui s'entend au sens large : seul le premier, pour une quantité entière naturelle, prouve qu'un processus s'arrête.

Signal : l'énoncé répète une opération (« à chaque étape », « on recommence »), ou définit des suites par récurrence et demande de montrer qu'une expression est constante.
1) Nommer les états successifs et la quantité : « Pour tout $k$, notons $S_k$ la somme des nombres écrits après $k$ étapes. »
2) Isoler une étape quelconque, décrite avec des lettres : « Soit $k$ tel que l'étape $k+1$ ait lieu ; elle efface deux nombres $a$ et $b$ et écrit $c$. » Aucun exemple chiffré ne remplace ce calcul.
3) Calculer la variation en traitant tous les types d'étape, par une disjonction de cas s'il y en a plusieurs, puis conclure : « Dans tous les cas, $S_{k+1} = S_k$ », ou « $S_{k+1} - S_k$ est pair, donc $S_{k+1} \equiv S_k \ [2]$ ».
4) Propager par récurrence : « Pour $k \in \mathbb{N}$, notons $P(k)$ l'assertion « $S_k = S_0$ ». » L'initialisation est immédiate ; l'hérédité cite le calcul de 3), puis l'hypothèse de récurrence : « $S_{k+1} = S_k$ d'après ce qui précède ; or $S_k = S_0$ par hypothèse de récurrence ; donc $S_{k+1} = S_0$. »
5) Conclure : « Par récurrence, $S_k = S_0$ pour tout $k$ : la somme est conservée. » Si le processus compte exactement $N$ étapes, ou si l'on a fixé une suite de $N$ étapes, la récurrence porte sur $k \in \llbracket 0, N \rrbracket$ et l'hérédité sur $k \in \llbracket 0, N - 1 \rrbracket$. Si l'on ignore combien d'étapes le processus compte, l'assertion porte sur tout $k$ tel que le processus compte au moins $k$ étapes, et l'hérédité sur tout $k$ tel que l'étape $k+1$ ait lieu.

Soient $(u_n)$ et $(v_n)$ les suites définies par $u_0 = 1$, $v_0 = 0$ et, pour tout $n \in \mathbb{N}$, $u_{n+1} = \frac{3u_n + 4v_n}{5}$ et $v_{n+1} = \frac{4u_n - 3v_n}{5}$. Montrer que la suite $(u_n^2 + v_n^2)$ est constante, puis que $\lvert u_n \rvert \le 1$ pour tout $n \in \mathbb{N}$.
Pour tout $n \in \mathbb{N}$, posons $w_n = u_n^2 + v_n^2$.
Soit $n \in \mathbb{N}$. Par définition des suites, $w_{n+1} = \frac{(3u_n + 4v_n)^2 + (4u_n - 3v_n)^2}{25}$.
En développant, $(3u_n + 4v_n)^2 = 9u_n^2 + 24u_n v_n + 16v_n^2$ et $(4u_n - 3v_n)^2 = 16u_n^2 - 24u_n v_n + 9v_n^2$.
Donc $w_{n+1} = \frac{25u_n^2 + 25v_n^2}{25} = w_n$.
Ainsi, pour tout $n \in \mathbb{N}$, $w_{n+1} = w_n$.
Pour $n \in \mathbb{N}$, notons $P(n)$ l'assertion « $w_n = 1$ ».
Initialisation : $w_0 = 1^2 + 0^2 = 1$, donc $P(0)$ est vraie.
Hérédité : soit $n \in \mathbb{N}$ tel que $P(n)$ soit vraie. D'après ce qui précède, $w_{n+1} = w_n$ ; or $w_n = 1$ par hypothèse de récurrence ; donc $w_{n+1} = 1$ et $P(n+1)$ est vraie.
Par récurrence, $P(n)$ est vraie pour tout $n \in \mathbb{N}$ : la suite $(u_n^2 + v_n^2)$ est constante, égale à $1$.
Soit $n \in \mathbb{N}$. Comme $v_n^2 \ge 0$, on a $u_n^2 \le u_n^2 + v_n^2 = 1$.
Par croissance de la fonction racine carrée sur $\mathbb{R}_+$, on en déduit $\lvert u_n \rvert = \sqrt{u_n^2} \le \sqrt{1} = 1$.
À retenir : on calcule l'effet d'une étape quelconque, du rang $n$ au rang $n+1$ avec $n$ fixé, puis la récurrence transporte la valeur initiale à tous les rangs.

On écrit au tableau les entiers de $1$ à $10$. À chaque étape, on choisit deux des nombres écrits, $a$ et $b$, on les efface et on écrit $\lvert a - b \rvert$ ; on s'arrête lorsqu'il ne reste qu'un nombre. Montrer que ce dernier nombre est impair.
Chaque étape efface deux nombres et en écrit un, donc après $k$ étapes il reste $10 - k$ nombres.
On effectue une étape tant qu'il reste au moins deux nombres, et l'on s'arrête lorsqu'il n'en reste qu'un, c'est-à-dire lorsque $10 - k = 1$ ; donc le processus comporte exactement $9$ étapes et se termine sur un seul nombre.
Les nombres écrits restent des entiers naturels, car $\lvert a - b \rvert$ en est un dès que $a$ et $b$ en sont.
Pour $k \in \llbracket 0, 9 \rrbracket$, notons $S_k$ la somme des nombres écrits après $k$ étapes.
Soit $k \in \llbracket 0, 8 \rrbracket$. L'étape $k+1$ efface deux nombres $a$ et $b$ et écrit $\lvert a - b \rvert$, donc $S_{k+1} = S_k - a - b + \lvert a - b \rvert$.
Si $a \ge b$, alors $\lvert a - b \rvert = a - b$, donc $S_{k+1} = S_k - 2b$.
Si $a < b$, alors $\lvert a - b \rvert = b - a$, donc $S_{k+1} = S_k - 2a$.
Dans les deux cas, $S_{k+1} - S_k$ est pair, donc $S_{k+1}$ a la même parité que $S_k$.
Pour $k \in \llbracket 0, 9 \rrbracket$, notons $P(k)$ l'assertion « $S_k$ est impair ».
Initialisation : $S_0 = 1 + 2 + \cdots + 10 = \frac{10 \times 11}{2} = 55$, qui est impair, donc $P(0)$ est vraie.
Hérédité : soit $k \in \llbracket 0, 8 \rrbracket$ tel que $P(k)$ soit vraie. D'après ce qui précède, $S_{k+1}$ a la même parité que $S_k$, qui est impair par hypothèse de récurrence ; donc $P(k+1)$ est vraie.
Par récurrence, $S_k$ est impair pour tout $k \in \llbracket 0, 9 \rrbracket$.
Après $9$ étapes, il reste un seul nombre, égal à $S_9$ ; donc le dernier nombre est impair.
À retenir : l'étape est traitée pour deux nombres $a$ et $b$ quelconques et dans tous ses cas, puis l'on conclut avec la seule information conservée, la parité de la somme, et non la somme elle-même.

Ligne fautive : « Au départ, la somme vaut $55$ ; si l'on efface $1$ et $2$, on écrit $1$ et la somme vaut $53$, toujours impaire. Donc la parité de la somme est invariante. »
Ce calcul porte sur une étape particulière, depuis l'état initial : il ne dit rien des autres choix de $a$ et $b$, ni des étapes qui partent des états suivants. Être invariant est un énoncé « pour toute étape, depuis tout état », et un exemple ne démontre jamais un « pour tout ».
Version correcte : « Soit une étape quelconque, qui efface deux nombres $a$ et $b$ et écrit $\lvert a - b \rvert$. La somme varie de $\lvert a - b \rvert - a - b$, qui vaut $-2b$ si $a \ge b$ et $-2a$ sinon ; cette variation est paire, donc la parité de la somme est conservée. »

Situation : trois tas contiennent $a$, $b$ et $c$ jetons ; une étape retire un jeton à deux tas et en ajoute deux au troisième.
Ligne fautive : « Si l'on retire un jeton aux tas $1$ et $2$ et qu'on en ajoute deux au tas $3$, $a - b$ ne change pas ; donc $a - b$ est un invariant. »
L'étape peut porter sur n'importe quelle paire de tas. Sur les tas $1$ et $3$, l'état $(a, b, c)$ devient $(a - 1, b + 2, c - 1)$ et $a - b$ diminue de $3$ : la quantité $a - b$ n'est pas invariante, et rien de ce qu'on en déduirait ne serait démontré.
Version correcte : « L'étape a trois formes. Sur les tas $1$ et $2$, $a - b$ ne change pas ; sur les tas $1$ et $3$, il diminue de $3$ ; sur les tas $2$ et $3$, il augmente de $3$. Dans tous les cas, $a - b$ varie d'un multiple de $3$, donc son reste modulo $3$ est invariant. »

Signal : l'énoncé décrit une règle répétée et demande « peut-on obtenir… ? » ou « que vaut le dernier nombre ? », sans nommer la quantité à suivre.
1) Écrire une étape quelconque avec des lettres, sous toutes ses formes : « $a$ et $b$ sont remplacés par $c$ », « $(a, b, c)$ devient $(a - 1, b - 1, c + 2)$ ».
2) Calculer l'effet de cette étape sur les candidats usuels : la somme des nombres, leur produit, le nombre d'objets d'un type donné, la différence de deux compteurs, la somme des carrés.
3) Si la variation est nulle, le candidat est un invariant. Si elle ne l'est pas mais reste toujours un multiple d'un même entier $m$, souvent $2$ ou $3$, retenir le reste modulo $m$.
4) Si un calcul se factorise, transformer la quantité : puisque $ab + a + b + 1 = (a + 1)(b + 1)$, remplacer $a$ et $b$ par $ab + a + b$ conserve le produit des $x + 1$.
5) Pour prouver une impossibilité, calculer le candidat dans l'état initial et dans l'état visé, et ne le garder que s'il y prend des valeurs différentes ; sinon, même s'il est invariant, il ne prouve rien, et l'on revient en 2). Pour déterminer l'état final, garder un candidat dont la valeur sur un état d'arrêt détermine cet état : sur un seul nombre $z$, la somme vaut $z$ et le produit des $x + 1$ vaut $z + 1$.
Indices : « impair » oriente vers une parité, « multiple de $3$ » vers un reste modulo $3$, « le dernier nombre » vers une quantité qui, sur un seul nombre, redonne ce nombre ou une expression simple de ce nombre.

Chaque ligne se redémontre sur une étape quelconque avant d'être utilisée sur une copie.

On écrit au tableau les nombres $1$, $2$, $3$, $4$ et $5$. À chaque étape, on efface deux nombres $a$ et $b$ et on écrit $ab + a + b$. Montrer qu'après $4$ étapes il reste un seul nombre, et qu'il vaut $719$ quels que soient les choix effectués.
Chaque étape efface deux nombres et en écrit un, donc après $k$ étapes il reste $5 - k$ nombres ; après $4$ étapes, il en reste un seul.
Pour tout état du tableau, où sont écrits les nombres $x_1, \dots, x_p$ avec leurs répétitions, posons $Q = (x_1 + 1)(x_2 + 1) \cdots (x_p + 1)$.
Soit une étape quelconque, qui efface deux nombres $a$ et $b$ et écrit $c = ab + a + b$. Notons $R$ le produit des $x_i + 1$ pour les autres nombres écrits, avec $R = 1$ s'il n'y en a pas.
Avant l'étape, $Q = (a + 1)(b + 1)R$ ; après l'étape, $Q$ prend la valeur $Q' = (c + 1)R$.
Or $c + 1 = ab + a + b + 1 = (a + 1)(b + 1)$, donc $Q' = (a + 1)(b + 1)R = Q$.
Fixons des choix quelconques pour les $4$ étapes. Pour $k \in \llbracket 0, 4 \rrbracket$, notons $Q_k$ la valeur de $Q$ après les $k$ premières de ces étapes, et $P(k)$ l'assertion « $Q_k = 720$ ».
Initialisation : $Q_0 = 2 \times 3 \times 4 \times 5 \times 6 = 720$, donc $P(0)$ est vraie.
Hérédité : soit $k \in \llbracket 0, 3 \rrbracket$ tel que $P(k)$ soit vraie. D'après ce qui précède, l'étape $k+1$ conserve $Q$, donc $Q_{k+1} = Q_k$ ; or $Q_k = 720$ par hypothèse de récurrence ; donc $P(k+1)$ est vraie.
Par récurrence, $Q_4 = 720$.
Notons $z$ le nombre qui reste après ces $4$ étapes. Alors $Q_4 = z + 1$, donc $z + 1 = 720$, c'est-à-dire $z = 719$.
Comme les choix sont quelconques, le dernier nombre vaut $719$ quels que soient les choix effectués.
À retenir : ni la somme ni le produit ne sont conservés ; c'est la factorisation de $ab + a + b + 1$ qui désigne la quantité à suivre, que l'on évalue au départ puis à l'arrivée, pour une suite de choix quelconque.

Signal : « Peut-on obtenir… ? », « Est-il possible d'arriver à… ? », « Montrer qu'on n'obtiendra jamais… ».
1) Fixer une suite d'étapes quelconque : « Soient $N \in \mathbb{N}$ et une suite de $N$ étapes partant de l'état initial ; notons $x_0, x_1, \dots, x_N$ les états successifs. »
2) Démontrer que la quantité choisie $f$ est conservée, ou que son reste l'est : « Pour tout $k \in \llbracket 0, N \rrbracket$, $f(x_k) = f(x_0)$ », ou, pour un reste modulo $m$ : « Pour tout $k \in \llbracket 0, N \rrbracket$, $f(x_k) \equiv f(x_0) \ [m]$. »
3) Calculer la valeur au départ : « Au départ, $f(x_0) = \dots$ »
4) Calculer la valeur dans chaque état visé, s'il y en a plusieurs : « Or tout état où … vérifie $f = \dots$ »
5) Comparer et conclure : « Ces valeurs sont différentes (ou ces restes sont différents), donc $x_N$ n'est pas un état visé. Comme $N$ et les étapes sont quelconques, aucun état visé n'est accessible. » Puis répondre à la question posée : « On ne peut donc pas … ».
Variante par l'absurde : « Supposons qu'il existe une suite de $N$ étapes menant de $x_0$ à $y$. Alors $f(y) = f(x_0)$, ce qui contredit $f(y) \neq f(x_0)$. »
Si les deux valeurs sont égales, on n'a rien démontré, ni l'impossibilité ni la possibilité : on change d'invariant.

Trois tas contiennent $5$, $7$ et $9$ jetons. À chaque étape, on choisit deux tas non vides, on retire un jeton à chacun et on ajoute deux jetons au troisième tas. Peut-on, après un certain nombre d'étapes, réunir les $21$ jetons dans un seul tas ?
Soient $N \in \mathbb{N}$ et une suite de $N$ étapes partant de l'état initial. Pour $k \in \llbracket 0, N \rrbracket$, notons $a_k$, $b_k$ et $c_k$ les nombres de jetons des tas $1$, $2$ et $3$ après $k$ étapes, et posons $d_k = a_k - b_k$.
Soit $k \in \llbracket 0, N - 1 \rrbracket$. L'étape $k+1$ porte sur deux des trois tas ; trois cas se présentent.
Si elle porte sur les tas $1$ et $2$, alors $a_{k+1} = a_k - 1$ et $b_{k+1} = b_k - 1$, donc $d_{k+1} = d_k$.
Si elle porte sur les tas $1$ et $3$, alors $a_{k+1} = a_k - 1$ et $b_{k+1} = b_k + 2$, donc $d_{k+1} = d_k - 3$.
Si elle porte sur les tas $2$ et $3$, alors $a_{k+1} = a_k + 2$ et $b_{k+1} = b_k - 1$, donc $d_{k+1} = d_k + 3$.
Dans tous les cas, $d_{k+1} - d_k$ est un multiple de $3$, donc $d_{k+1} \equiv d_k \ [3]$.
Pour $k \in \llbracket 0, N \rrbracket$, notons $P(k)$ l'assertion « $d_k \equiv 1 \ [3]$ ».
Initialisation : $d_0 = 5 - 7 = -2 = 3 \times (-1) + 1$, donc $d_0 \equiv 1 \ [3]$ et $P(0)$ est vraie.
Hérédité : soit $k \in \llbracket 0, N - 1 \rrbracket$ tel que $P(k)$ soit vraie. D'après ce qui précède, $d_{k+1} \equiv d_k \ [3]$ ; or $d_k \equiv 1 \ [3]$ par hypothèse de récurrence ; donc $d_{k+1} \equiv 1 \ [3]$ et $P(k+1)$ est vraie.
Par récurrence, $P(k)$ est vraie pour tout $k \in \llbracket 0, N \rrbracket$ ; en particulier, $d_N \equiv 1 \ [3]$.
Or les états où les $21$ jetons forment un seul tas sont $(21, 0, 0)$, $(0, 21, 0)$ et $(0, 0, 21)$ ; la différence entre les deux premiers tas y vaut $21$, $-21$ et $0$, qui sont tous congrus à $0$ modulo $3$.
Comme $1 \not\equiv 0 \ [3]$, l'entier $d_N$ n'est égal à aucune de ces trois différences ; donc, après ces $N$ étapes, les $21$ jetons ne forment pas un seul tas.
Comme $N$ et la suite d'étapes sont quelconques, on ne peut jamais réunir les $21$ jetons dans un seul tas : la réponse est non.
À retenir : le total des jetons est lui aussi conservé, mais il vaut $21$ au départ comme à l'arrivée et ne prouve rien ; on retient un invariant qui prend des valeurs différentes dans l'état initial et dans l'état visé, et l'on écrit la comparaison.

Ligne fautive : « Chaque étape conserve le nombre total de jetons, égal à $21$ ; on ne peut donc pas réunir les $21$ jetons dans un seul tas. »
Le total est bien invariant, mais il vaut aussi $21$ dans l'état visé $(21, 0, 0)$ : un invariant qui prend la même valeur au départ et à l'arrivée est compatible avec les deux états et ne démontre rien. Seul un invariant qui prend des valeurs différentes prouve l'impossibilité.
Version correcte : « Chaque étape conserve le reste de $a - b$ modulo $3$. Il vaut $1$ au départ, car $5 - 7 = -2 \equiv 1 \ [3]$, et $0$ dans chacun des états $(21, 0, 0)$, $(0, 21, 0)$ et $(0, 0, 21)$. Donc aucun de ces états n'est accessible. »

Ligne fautive : « Après de nombreux essais, aucune suite d'étapes ne réunit les $21$ jetons dans un seul tas ; c'est donc impossible. »
Une impossibilité est la négation d'une existence : elle affirme que toutes les suites d'étapes échouent, et il y en a une infinité. Des essais n'en examinent qu'un nombre fini ; ils peuvent suggérer un invariant, jamais remplacer sa démonstration.
Version correcte : « Soient $N \in \mathbb{N}$ et une suite quelconque de $N$ étapes. Montrons par récurrence que, pour tout $k \in \llbracket 0, N \rrbracket$, $a_k - b_k \equiv 1 \ [3]$. » La preuve qui suit ne choisit aucune étape particulière.

Situation : les entiers de $1$ à $10$ sont écrits au tableau, et une étape remplace deux nombres $a$ et $b$ par $\lvert a - b \rvert$.
Ligne fautive : « La parité de la somme est conservée et $55$ est impair, donc on peut terminer avec le nombre $55$. »
L'invariant fournit une condition nécessaire : tout état accessible a une somme impaire. Conclure qu'un état de somme impaire est accessible, c'est utiliser la réciproque, qui est fausse ici : comme $\lvert a - b \rvert \le \max(a, b)$, aucun nombre écrit ne dépasse jamais $10$, et $55$ est inaccessible.
Version correcte : pour prouver qu'un état est accessible, on exhibe des étapes qui y mènent. « En effaçant $2$ et $1$, puis $4$ et $3$, $6$ et $5$, $8$ et $7$, $10$ et $9$, on obtient cinq fois le nombre $1$. En effaçant deux $1$, puis encore deux $1$, il reste $0$, $0$ et $1$. En effaçant $0$ et $0$, puis $0$ et $1$, il reste $1$. Donc on peut terminer avec le nombre $1$. »

On appelle ici variant d'un processus une quantité $\varphi$ à valeurs dans $\mathbb{N}$ telle que $\varphi(x') < \varphi(x)$ pour toute étape $x \to x'$ ; entre entiers, cela revient à $\varphi(x') \le \varphi(x) - 1$. Un processus qui admet un variant s'arrête toujours, quelles que soient les étapes choisies, et au bout d'au plus $\varphi(x_0)$ étapes. Invariant et variant jouent des rôles distincts : l'invariant restreint les états que l'on peut atteindre, le variant limite le nombre d'étapes. Le mot vient de l'algorithmique, où il prouve qu'une boucle se termine.

Il n'existe pas de suite $(n_k)_{k \in \mathbb{N}}$ d'entiers naturels telle que $n_{k+1} < n_k$ pour tout $k \in \mathbb{N}$ : on aurait $n_{k+1} \le n_k - 1$, donc $n_k \le n_0 - k$ pour tout $k$ par récurrence, puis $n_{n_0 + 1} \le -1$, ce qui est absurde (voir le thème Descente infinie). Le résultat tombe en défaut pour les entiers relatifs, avec $n_k = -k$, et pour les réels positifs, avec $n_k = \frac{1}{k+1}$. Une suite d'entiers naturels qui décroît seulement au sens large peut aussi être infinie : il suffit qu'elle soit constante.

Signal : « Montrer que le processus s'arrête », « se termine », « ne peut pas se poursuivre indéfiniment », ou une opération répétée « tant que » une condition est remplie.
1) Préciser quand le processus s'arrête : lorsque plus aucune étape n'est possible (moins de deux boules, deux nombres égaux).
2) Choisir une quantité $\varphi$ et vérifier qu'elle est un entier naturel dans tout état atteint, au besoin par récurrence sur le nombre d'étapes : « Les nombres écrits restent des entiers naturels non nuls, donc $\varphi$ est à valeurs dans $\mathbb{N}$. »
3) Démontrer, pour une étape quelconque $x \to x'$, la décroissance stricte : « $\varphi(x') \le \varphi(x) - 1$ ».
4) Conclure en citant la propriété de $\mathbb{N}$ : « Supposons par l'absurde qu'il existe une suite infinie d'étapes, et notons $x_k$ l'état obtenu après $k$ étapes, pour tout $k \in \mathbb{N}$. Alors $(\varphi(x_k))_{k \in \mathbb{N}}$ est une suite strictement décroissante d'entiers naturels, ce qui est impossible. Donc le processus s'arrête. »
Variante directe : par récurrence, $\varphi(x_k) \le \varphi(x_0) - k$ tant que les étapes ont lieu ; comme $\varphi(x_k) \ge 0$, on a $k \le \varphi(x_0)$, donc le processus s'arrête après au plus $\varphi(x_0)$ étapes.
Lorsque la règle laisse des choix, « le processus s'arrête » signifie que toute suite d'étapes est finie : on raisonne sur une suite d'étapes quelconque.

On part d'un couple $(a, b)$ d'entiers naturels non nuls. Tant que les deux nombres sont différents, on remplace le plus grand par la différence du plus grand et du plus petit. Montrer que le processus s'arrête.
Le processus s'arrête lorsque les deux nombres du couple sont égaux.
Pour tout couple $(x, y)$ d'entiers naturels non nuls, posons $\varphi(x, y) = x + y$.
Soient $(x, y)$ un couple d'entiers naturels non nuls tel que $x \neq y$, et $(x', y')$ le couple obtenu après une étape.
Si $x > y$, alors $(x', y') = (x - y, y)$ ; $x - y$ est un entier naturel non nul car $x > y$, et $\varphi(x', y') = x = \varphi(x, y) - y \le \varphi(x, y) - 1$ car $y \ge 1$.
Si $x < y$, alors $(x', y') = (x, y - x)$ ; $y - x$ est un entier naturel non nul car $y > x$, et $\varphi(x', y') = y = \varphi(x, y) - x \le \varphi(x, y) - 1$ car $x \ge 1$.
Dans les deux cas, $(x', y')$ est encore un couple d'entiers naturels non nuls, et $\varphi(x', y') \le \varphi(x, y) - 1$.
Le couple de départ est formé d'entiers naturels non nuls ; par récurrence sur le nombre d'étapes, tous les couples obtenus le sont aussi, donc $\varphi$ ne prend que des valeurs entières naturelles.
Supposons par l'absurde que le processus ne s'arrête pas, et notons $(a_k, b_k)$ le couple obtenu après $k$ étapes, pour tout $k \in \mathbb{N}$.
D'après ce qui précède, $a_{k+1} + b_{k+1} \le a_k + b_k - 1$ pour tout $k \in \mathbb{N}$ : la suite $(a_k + b_k)_{k \in \mathbb{N}}$ est une suite strictement décroissante d'entiers naturels, ce qui est impossible.
Donc le processus s'arrête.
À retenir : on nomme la quantité, on vérifie qu'elle reste dans $\mathbb{N}$, on prouve qu'une étape quelconque la fait baisser strictement, puis on cite l'absence de suite strictement décroissante d'entiers naturels.

Situation : l'algorithme des soustractions, qui remplace le plus grand de deux entiers naturels non nuls distincts par leur différence.
Ligne fautive : « Le plus petit des deux nombres décroît à chaque étape, donc le processus s'arrête. »
De $(5, 2)$, on passe à $(3, 2)$ : le plus petit nombre reste égal à $2$. Il ne décroît qu'au sens large, et une suite d'entiers qui décroît au sens large peut être infinie, par exemple constante. De même, une quantité réelle positive peut décroître strictement sans fin, comme $\frac{1}{k+1}$ : l'argument exige des entiers naturels et une décroissance stricte.
Version correcte : « La somme des deux nombres est un entier naturel, et chaque étape la diminue du plus petit des deux, qui vaut au moins $1$. Comme il n'existe pas de suite strictement décroissante d'entiers naturels, le processus s'arrête. »

Signal : « Montrer que le dernier nombre est… », « Quelle est la couleur de la dernière boule ? », « Que reste-t-il à la fin ? ».
1) Prouver que le processus s'arrête, par un variant ou en comptant les étapes, puis décrire les états d'arrêt possibles : « Le processus s'arrête, et il reste alors une seule boule. »
2) Démontrer qu'une quantité est conservée : pour une étape quelconque, puis par récurrence.
3) Écrire que cette quantité a, dans l'état final, sa valeur de départ : « Le nombre de boules blanches est impair au départ, donc il est impair dans l'état final. »
4) Parmi les états d'arrêt possibles, garder ceux qui ont cette valeur, et conclure : « Il reste une seule boule et le nombre de boules blanches est impair, donc la dernière boule est blanche. »
Les deux quantités n'ont pas le même rôle : celle qui décroît strictement dit que le processus s'arrête, l'invariant dit dans quel état.

Un sac contient $5$ boules blanches et $6$ boules noires ; on dispose à côté d'une réserve de boules des deux couleurs. Tant que le sac contient au moins deux boules, on en tire deux, que l'on ne remet pas ; si elles sont de même couleur, on met une boule noire dans le sac, sinon on y met une boule blanche. Montrer que le processus s'arrête et que la dernière boule est blanche.
Pour tout entier naturel $k$ tel que le processus compte au moins $k$ tirages, notons $N_k$ le nombre de boules du sac et $B_k$ le nombre de boules blanches après $k$ tirages ; ainsi $N_0 = 11$ et $B_0 = 5$.
Chaque tirage retire deux boules du sac et en ajoute une, donc $N_{k+1} = N_k - 1$ lorsque le tirage $k+1$ a lieu.
Arrêt. Supposons par l'absurde que le processus ne s'arrête pas. Alors $N_k$ est défini pour tout $k \in \mathbb{N}$, et $(N_k)_{k \in \mathbb{N}}$ est une suite strictement décroissante d'entiers naturels, ce qui est impossible. Donc le processus s'arrête.
État final. Un tirage n'a lieu que si le sac contient au moins deux boules, et il en laisse alors au moins une ; comme $N_0 \ge 1$, le sac n'est jamais vide. Le processus s'arrête lorsque le sac contient moins de deux boules, donc sur un sac qui en contient exactement une.
Invariant. Soit $k$ tel que le tirage $k+1$ ait lieu.
Si les deux boules tirées sont blanches, on ajoute une noire, donc $B_{k+1} = B_k - 2$.
Si elles sont noires, on ajoute une noire, donc $B_{k+1} = B_k$.
Si elles sont de couleurs différentes, on retire une blanche et on en ajoute une, donc $B_{k+1} = B_k$.
Dans tous les cas, $B_{k+1} - B_k$ est pair, donc $B_{k+1}$ a la même parité que $B_k$.
Pour tout $k$ tel que le processus compte au moins $k$ tirages, notons $P(k)$ l'assertion « $B_k$ est impair ».
Initialisation : $B_0 = 5$ est impair, donc $P(0)$ est vraie.
Hérédité : soit $k$ tel que $P(k)$ soit vraie et que le tirage $k+1$ ait lieu. D'après ce qui précède, $B_{k+1}$ a la même parité que $B_k$, qui est impair par hypothèse de récurrence ; donc $P(k+1)$ est vraie.
Par récurrence, le nombre de boules blanches est impair après chaque tirage.
Conclusion. Dans l'état final, le sac contient une seule boule, donc le nombre de boules blanches vaut $0$ ou $1$ ; ce nombre est impair, donc il vaut $1$ : la dernière boule est blanche.
À retenir : le nombre de boules, qui décroît strictement, prouve l'arrêt ; la parité du nombre de boules blanches, qui est conservée, fixe l'état final.

Ligne fautive : « La parité du nombre de boules blanches ne change pas au cours des tirages, donc le processus s'arrête. »
Un invariant ne fait jamais avancer un processus : si l'on remettait dans le sac les deux boules tirées, cette parité serait encore conservée et le processus ne s'arrêterait jamais. Inversement, « le nombre de boules diminue, donc la dernière boule est blanche » est tout aussi faux : une quantité qui décroît strictement prouve l'arrêt, elle ne dit rien de l'état final.
Version correcte : « Le nombre de boules est un entier naturel qui diminue de $1$ à chaque tirage, donc le processus s'arrête. La parité du nombre de boules blanches est conservée, donc la dernière boule est blanche. »

« Soit une étape quelconque » introduit une étape arbitraire, sur laquelle on démontre la conservation : c'est ce qui la rend valable pour toutes. « Dans tous les cas » clôt la disjonction sur les formes possibles de l'étape. « Par récurrence » étend la conservation d'une étape à un nombre quelconque d'étapes. « Or » introduit un second fait qui, joint au précédent, permet de conclure : dans l'hérédité, l'hypothèse de récurrence ; dans une preuve d'impossibilité, la valeur de l'invariant dans l'état visé, qui contredit la valeur conservée. « Comme $N$ et les étapes sont quelconques » transforme la conclusion obtenue pour une suite d'étapes en une impossibilité pour toutes.