Exercice 4 — Algorithme de KAPREKAR

Sujet

1. Cas d'un entier à 2 chiffres :

On s'intéresse ici aux entiers compris entre 0 et 99 .

• Pour un nombre supérieur ou égal à 10 , son retourné est obtenu en inversant ces deux chiffres. Exemple : le retourné de 49 est 94.
• Pour les nombres strictement inférieurs à 10 , on considère l'entier avec un zéro à gauche supplémentaire et le retourné est alors obtenu en inversant ces deux chiffres. Exemple : 7 est considéré comme 07 et son retourné est le nombre 70 .

On s'intéresse à l'algorithme suivant, dit algorithme de Kaprekar :

• Prendre un nombre entier, par exemple 28.
• Ordonner ses chiffres du plus grand au plus petit : ici 82 .
• Puis soustraire du nombre obtenu le retourné de ce dernier nombre : ici, on obtient \(82-28=54\).

On peut recommencer la \(2^{\text {ème }}\) et la \(3^{\text {ème }}\) étape indéfiniment à partir de la différence obtenue : \(54-45=09\), \(90-09=81, \ldots\)
On souhaite étudier ce qui se passe lorsqu'on répète cet algorithme.
a) Appliquer l'algorithme de Kaprekar au nombre 22. Que remarque-t-on? Peut-on généraliser?
b) Appliquer l'algorithme de Kaprekar 10 fois de suite au nombre 59. Que remarque-t-on?
c) Cas général d'un entier avec 2 chiffres distincts :

Soit \(a\) et \(b\) deux chiffres; on note \(\overline{a b}\) l'entier dont le chiffre des dizaines est \(a\) et le chiffre des unités est \(b\). On a ainsi \(\overline{a b}=10 a+b\).
Quitte à réordonner les chiffres on peut supposer que \(a>b\).
i. Montrer que \(\overline{a b}-\overline{b a}=9(a-b)\).
ii. Quelles sont les valeurs que peut prendre \(a-b\) ? Et donc \(\overline{a b}-\overline{b a}\) ? En appliquant plusieurs fois de suite l'algorithme de Kaprekar à chacune de ces dernières valeurs, montrer que l'on aboutit toujours en un nombre fini d'étapes au cycle :

\[ 81-63-27-45-09 \]

2. Cas d'un entier à 3 chiffres :

On souhaite généraliser cet algorithme aux cas des entiers à 3 chiffres en définissant de la même façon le retourné d'un entier. Exemple :

• si on prend le nombre entier 231 , en réordonnant ses chiffres cela donne 321 et son retourné est le nombre 123;
• si on prend le nombre entier 32,32 est considéré comme 032 , en réordonnant ses chiffres cela donne 320 et son retourné est le nombre 023 ;
• si on prend le nombre entier 7,7 est considéré comme 007, en réordonnant ses chiffres cela donne 700 et son retourné est le nombre 007.
  a) Expliquer ce qui se passe lorsque les 3 chiffres sont égaux.