Sujet
Soit \(N\) un entier naturel non nul. On choisit au hasard un de ses diviseurs stricts, qui remplace \(N\) dans l'algorithme, et on recommence jusqu'à obtenir 1. On compte une seconde entre deux choix successifs. Il s'agit de déterminer la duée moyenne des séquences conduisant de \(N\) à 1 .
- Dans cet exemple, \(N=12\). Les suites possibles sont : \((12,6,3,1),(12,6,2,1),(12,6,1),(12,4\), \(2,1),(12,4,1),(12,3,1),(12,2,1),(12,1)\).
«Facile, dit Bob, il y a trois séquences durant 3 secondes, quatre durant 2 secondes et une durant une seconde; la moyenne est donc \(\frac{3 \times 3+4 \times 2+1 \times 1}{8}\), c'est-à-dire \(2,125 \mathrm{~s} \gg\).
« Non, dit Alice, la durée moyenne d'une séquence est \(\frac{61}{30}\) ».
Qui a raison? - On donne les deux nombres \(N=35\) et \(P=1225\). On précise que \(N=5 \times 7\) et que \(P=N^{2}\). Quelle est la durée moyenne des séquences conduisant de \(P\) à 1 ?
- Les suites possibles n'ont pas toutes la même fréquence d'occurrence. Faisons un arbre. De haut en bas, les probabilités d'occurrence qu'on peut attribuer à chacune des branches sont :
\(\frac{1}{5} \times \frac{1}{3}\) pour chacune des trois premières,
\(\frac{1}{5} \times \frac{1}{2}\) pour les deux suivantes,
puis \(\frac{1}{5}\) pour chacune des trois dernières.
L'espérance matématique du temps de calcul est donc :
\(T=\frac{1}{5}\left(3 \times\left(\frac{1}{3}+\frac{1}{3}+\frac{1}{2}\right)+2 \times\left(\frac{1}{3}+\frac{1}{2}+2\right)+1\right)\),
soit \(T=\frac{61}{30}\).