Défi Turing

Accueil - Enoncés -


Problème 230

Tri aléatoire

Un jeu de n cartes, numérotées de 1 à n, est mélangé de manière aléatoire de telle sorte que chaque permutation soit équiprobable. On doit trier ces cartes dans l'ordre croissant en utilisant la technique suivante :
  1. On observe la séquence de cartes. Si elle est déjà triée, alors il n'y a pas besoin de poursuivre l'action. Dans le cas contraire, si des séquences de cartes se trouvent rangées par ordre croissant sans « trou », alors ces séquences forment des groupes de cartes que l’on agrafe entre elles.
    Par exemple, avec 7 cartes initialement dans l'ordre 4 1 2 3 7 5 6, les cartes 1, 2 et 3 seront agrafées ensemble, ainsi que les cartes 5 et 6 (on obtient ainsi un groupe de 3 cartes, un groupe de 2 cartes et 2 cartes isolées).
  2. Les cartes sont alors «mélangées» en étant jetées en l'air (les cartes agrafées restent évidemment rangées entre elles). Les cartes (ou paquets de cartes agrafées) sont ensuite ramassées au hasard. On suppose que tous les ramassages possibles sont équiprobables, en dépit du fait que certaines cartes sont seules, et d'autres regroupées.
  3. On répète les étapes 1 et 2 jusqu'à ce que les cartes soient toutes triées.
Soit S(n) le nombre moyen de lancers nécessaires pour trier toutes les cartes (il s’agit donc d'une espérance). Puisque l'ordre est vérifié avant le premier lancer, on a donc S(1) = 0.
On donne également S(2) = 1, S(3) = 7/3, S(4) = 47/13 et S(5) = 4213/871.

Que vaut S(10) ? On saisira les 11 premiers chiffres de la réponse, en omettant la virgule.

précédent
suivant