Exercice 2 — L'algorithme réducteur — Olympiades 2016 La Réunion

Sujet

On considère l'algorithme suivant :

Variables :x;y;z;t
Début :
    - Affecter à x un entier aléatoire compris entre 0 et 999
    - Affecter à y le triple de x
    - Affecter à z la somme des chiffres de y
    - Affecter à t le tiers de z
    - Afficher t
Fin

On se propose de tester l'algorithme sur quelques valeurs.

Compléter le tableau ci-dessous comme dans l'exemple donné dans la première colonne.

Si \(x=1\)	816	10	333	670
alors l'algorithme affiche	6

On souhaite démontrer, dans le cas d'un nombre entier \(N\) à 4 chiffres, la proposition suivante :
«Si un nombre entier \(N\) est divisible par 3, alors la somme \(S\) de ses chiffres est divisible par 3, et réciproquement, tout entier \(N\) dont la somme \(S\) des chiffres est divisible par 3, est divisible par \(3 \gg\).
On rappelle que si on note \(a\) le chiffre des milliers, \(b\) le chiffre des centaines, \(c\) le chiffre des dizaines et \(d\) le chiffre des unités d'un nombre \(N\) de 4 chiffres, alors

\[ N=1000 a+100 b+10 c+d . \]

a) Exprimer la somme \(S\) des chiffres de \(N\) en fonction de \(a, b, c\) et \(d\).
b) Montrer que \(N-S\) est divisible par 3.
c) En déduire que si \(N\) est divisible par 3, alors \(S\) est divisible par 3 .
d) De même, démontrer que si \(S\) est divisible par 3, alors \(N\) est divisible par 3.
3. Démontrer que l'algorithme affiche toujours un entier, et que cet entier est toujours compris entre 0 et 9 . (On rappelle que \(0 \leqslant x \leqslant 999\) )
4. Afin de conjecturer si certains nombres ont plus de chances d'être affichés par l'algorithme réducteur que d'autres, on a programmé un algorithme qui calcule la fréquence d'affichage d'un nombre donné sur 10 000 essais. Celui-ci a permis d'obtenir par exemple les résultats suivants :

La fréquence d'affichage du nombre 1 par l'algorithme réducteur sur 10000 essais est 0,0188
La fréquence d'affichage du nombre 9 par l'algorithme réducteur sur 10000 essais est 0,0102
La fréquence d'affichage du nombre 1 par l'algorithme réducteur sur 10000 essais est 0,0194
La fréquence d'affichage du nombre 5 par l'algorithme réducteur sur 10000 essais est 0,2249

On considère l'algorithme suivant :

Variables :x;y;z;t
Début :
    - Affecter à x un entier aléatoire compris entre 0 et 999
    - Affecter à y le triple de x
    - Affecter à z la somme des chiffres de y
    - Affecter à t le tiers de z
    - Afficher t
Fin

On se propose de tester l'algorithme sur quelques valeurs.

Compléter le tableau ci-dessous comme dans l'exemple donné dans la première colonne.

Si \(x=1\)	816	10	333	670
alors l'algorithme affiche	6	\(\mathbf{1}\)	\(\mathbf{9}\)	\(\mathbf{1}\)

\(N=1000 a+100 b+10 c+d\).
a) Exprimer la somme \(S\) des chiffres de \(N\) en fonction de \(a, b, c\) et \(d\).
\(S=a+b+c+d\).
b) Montrer que \(N-S\) est divisible par 3.

\[ \begin{aligned} & N-S=1000 a+100 b+10 c+d-(a+b+c+d) \\ & N-S=999 a+99 b+9 c \\ & N-S=3(333 a+33 b+3 c) \end{aligned} \]

c) Ainsi, si \(N\) est divisible par 3, c'est-à-dire s'écrit \(3 k\) avec \(k\) entier, alors \(S=3 k-3(333 a+33 b+3 c)= 3[k-(333 a+33 b+3 c)]\)
Donc \(S\) est aussi divisible par 3.
Réciproquement, si \(S\) est divisible par 3, c'est-à-dire s'écrit \(3 k\) avec \(k\) entier, alors \(N=3(333 a+33 b+ 3 c)+3 k=3[333 a+33 b+3 c+k]\).
Donc \(N\) est aussi divisible par 3.
d) De même, démontrer que si \(S\) est divisible par 3, alors \(N\) est divisible par 3 .
3. Démontrer que l'algorithme affiche toujours un entier, et que cet entier est toujours compris entre 0 et 9 . (On rappelle que \(0 \leqslant x \leqslant 999\) )

Puisque \(y\) est un multiple de \(3, z\) aussi d'après la propriété démontrée à la question 2). Donc \(t=\frac{z}{3}\) est un entier.