Exercice 1 — Algorithme de Kaprekar

Sujet

On considère l'algorithme suivant :
Variables : N, G, P, k et nombreboucles sont des entiers naturels.

• Choisir nombreboucles
• Choisir un nombre N à deux chiffres
• Pourk allant de 1 à nombreboucles
• Former le nombre G, qui est le plus grand possible avec les deux chiffres composant ce nombre
• Former le nombre P , qui est le plus petit possible avec les deux chiffres composant ce nombre
• N prend la valeur \(\mathrm{G}-\mathrm{P}\)
• Afficher N

Par exemple, si on choisit nombreboucles \(=2\) et \(\mathrm{N}=70\), l'algorithme affiche successivement les nombres suivants :
\(-\mathrm{N}=63\), car \(\mathrm{G}=70\) et \(\mathrm{P}=07\);

• \(\mathrm{N}=27\).

1. Faire fonctionner l'algorithme avec les valeurs nombreboucles \(=3\) et \(\mathrm{N}=77\) puis avec les valeurs nombreboucles \(=8\) et \(\mathrm{N}=70\) et enfin avec les valeurs nombreboucles \(=8\) et \(\mathrm{N}=13\). Vous préciserez en particulier dans chaque situation, les valeurs affichées sur l'algorithme.
2. Dans cette question uniquement on suppose que le nombre N choisi au début de l'algorithme est formé de deux chiffres identiques.
   Quelle conjecture peut-on émettre sur les valeurs affichées par l'algorithme? Démontrer votre conjecture.
3. On suppose à présent que le nombre N choisi au début de l'algorithme est composé de deux chiffres différents. On rappelle que, si on note \(a\) le chiffre des dizaines et \(b\) le chiffre des unités, alors on \(\mathrm{a}: \mathrm{N}=10 a+b\).
   (a) Montrer que toutes les valeurs affichées par l'algorithme sont des multiples de 9 .
   (b) Montrer que les valeurs 99 et 00 ne seront jamais affichées par l'algorithme. On rappelle que dans cette question, on suppose que le nombre \(N\) choisi au début de l'algorithme est composé de deux chiffres différents.
   (c) Montrer que tous les nombres affichés par l'algorithme, sauf éventuellement le premier, sont des nombres impairs.
   (d) Montrer que si le nombre N choisi au début de l'algorithme s'écrit avec deux chiffres différents, alors les valeurs affichées par l'algorithme, sauf éventuellement la première, suivent un cycle de longueur 5.