Exercice 1 — L'algorithme de Kaprekar

Sujet

I. Un premier algorithme

Voici un algorithme applicable à des nombres de trois chiffres dont le chiffre des centaines n'est pas égal à celui des unités :

Étape 1 : Inverser l'ordre des chiffres (par exemple : 275 devient 572 ).
Étape 2 : Calculer la différence du plus grand et du plus petit de ces deux nombres.
Étape 3 : Réitérer l'étape 1 sur le nombre obtenu.
Étape 4 : Additionner ces deux derniers nombres.

1. a) Appliquer l'algorithme aux nombres 123, 448 et 946 .
   b) Que peut-on conjecturer?
2. Pour implémenter cet algorithme, l'étape 2, implicite lorsqu'on effectue les calculs «à la main», nécessite de dissocier l'entier saisi afin d'en isoler le chiffre des unités, celui des dizaines puis celui des centaines.

Compléter l'algorithme suivant dont le rôle est d'effectuer cette dissociation. Dans cet algorithme \(a\) est le chiffre de centaines, \(b\) celui des dizaines et \(c\) celui des unités du nombre \(n\) que l'on souhaite décomposer.

Entrée :

\[ n \text { est un entier naturel } \]

Initialisation :
Donner à \(a\) la valeur 0
Donner à \(b\) la valeur 0
Donner à \(c\) la valeur 0

Traitement :

Tant que \(n \geqslant 100\)
Affecter à \(a\) la valeur \(a+1\)
Affecter à \(n\) la valeur \(n-100\)
Fin Tant que
Tant que \(n \ldots .\). .
Affecter à \(b\) la valeur ......
Affecter à . . .la valeur . . . . . .
Fin Tant que
Affecter à \(c\) la valeur . . . . . .
Sortie :
Afficher \(a\)
Afficher \(b\)
Afficher \(c\)
3. On se propose maintenant de démontrer la conjecture établie en 1.b).

Pour cela, on choisit un nombre de trois chiffres que l'on écrit \(a b c\) où \(a, b\) et \(c\) sont donc des entiers compris entre 0 et 9 et représentent respectivement le chiffre des centaines, le chiffre des dizaines et le chiffre des unités de \(n\).
On peut, sans perdre de généralité, supposer \(a