Inscription / Connexion Nouveau Sujet
mélange de cartes à jouer
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) ?
Bonjour 
Le problème risque de ne pas être simple . S'intéresser directement au nombre moyen de lancers n'est pas forcément l'approche la plus simple . En fait chaque agrafage équivaux à une réduction du nombre de cartes on part donc d'un jeu J(10) à 10 cartes et on évolue vers un jeu avec 10 cartes ou moins , avec une probabilité donnée .
Il y a T=10! répartitions des 10 cartes , cette répartition aboutie à :
J(1) avec une probabilité 1/T .
J(2) avec une probabilité 9/T .
J(3) avec une probabilité 36/T .
...
Séparer les blocs revient à placer des bâtons entre les éléments rangés en ordre croissant . Le calcul n'est pas compliqué mais plutôt long .
Imod
En fait le calcul n'est pas aussi direct que ça car il faut séparer les blocs et les mélanger pour qu'ils ne fusionnent pas , il faut donc ajouter un dérangement . Je disais bien : pas simple .
Imod
L'exercice fait penser aux automates ou aux chaînes de Markov , le calcul direct est un travail d'Hercule . Les données fournies nous annoncent un lien mystérieux entre S(10) et certains des éléments fournis . Personnellement , le nombre moyen d'étapes ne parle pas , c'est un renseignement secondaire et je ne connais pas grand chose aux probas . Un travail pour Flight , Verdurin , Jandri ...
Imod
J'ai extrapolé jusqu'à S(10)
Si mon approche donnée le 01/04 
est correcte
Avec 10 cartes il faudrait environ 15 coups pour avoir la chaine complète:
Cliquez pour afficher
Je pense avoir trouvé un moyen de calculer de proche en proche les différentes probabilités mais c'est vraiment lourd .
Il y a deux éléments à prendre en compte :
O(n) : nombre de façons d'ordonner n entiers consécutifs de façon à ce que le successeur de k ne soit jamais k+1 .
O(1) = O(2) = 1 et O(n+2) = (n+1).O(n+1) + n.O(n) .
: nombre de façons de séparer n+1 entiers consécutifs en k+1 blocs d'entiers consécutifs .
Après on construit récursivement l'arbre de probabilités et on a la réponse . C'est très long et on n'utilise pas les renseignements fournis .
Imod
Je n'ai pas utilisé les S(2 à 5 ) donnés car je ne retrouve pas leur logique ,en effet
Pour S(4) 47/13 je trouve 108/24
En fait l'encadré que tu donnes est exactement ce que j'expliquais dans mon message précédent :
Ensuite l'arbre de probabilité est simple car les 4 blocs peuvent rester 4 avec une probabilité 11/24 et un chemin qui s'allonge à l'infini ou alors descendre vers un nombre moindre dont la longueur moyenne est déjà connue .
On peut donc calculer S(10) de proche en proche .
Imod
Annuler
connectez vous