Bon, je refais ma présentation vu que visiblement, la précédente n'avait pas plu ...

Mon prof de maths de seconde nous a soumis une énigme, une énigme de proba. Rapidement, on s'est aperçu qu'on pouvait pas faire d'arbre et ça s'est arrêté là.
Mais en cherchant un peu (pendant deux heures environ), j'ai trouvé une solution.
Un algorithme tellement merveilleux et intelligent que je me suis demandé qui d'autre le trouverait.

Je ne vais pas vous ré-expliquer toutes les règles et le principe, donc je vous donne le lien du topic où je l'ai postée :
http://minecraft.fr/forums/showthread.php?tid=7550

Vous pouvez poster là-bas, ou, si vous n'êtes pas inscrit et ne voulez pas vous inscrire, sur ce topic. Mais je ne visiterai pas souvent celui-là, je vous le dis tout de suite.

Bon, et ben, bonne chance

La premiere idee conne, c'est programmation dynamique. mais c'est un peu gros. Il y a 11^5 cases dans le tableau et l'algo est quadratique. donc 11^10. Ca va prendre quelques heures de calculs, mais c'est faisable.

Quelqu'un a mieux ?

Godrik On ne pourrait pas réduire un peu le travail ? Si on parvient à calculer les probabilités pour que les n°2, 3, 4, 5 et 6 arrivent en premier, alors on a toutes les probabilités souhaitées.

oui, il y a un argument de symmetrie qui marche: P(x1,x2,x3,x4,x5,x6,...x12) = P(x12,x11,x10,x9,..., x2,x1)
mais je ne pense pas que tu fasse plus que couper l'espace en 2.

C'est toi qui avait propose chaine de markov il me semble avant que je supprime l'autre topic. C'est une idee interessante, mais il y a aussi un nombre exponentiel d'etat a ta chaine de markov.

Je ne suis pas un bon probabiliste, mais tu peux tenter un raisonnement ou tu calcul la probabilite que 2 gagne en x iterations. ca veut dire qu'il y a 5 iterations qui sont 2 et x-5 iterations qui ne sont pas deux et qui ne sont pas 5 fois pareil. Si tu arrive a exprimer ca, il suffit de faire la somme sur x entre 5 et 11x5. Mais je ne suis pas completement sur que ca va rendre le calcul plus facil.

Soit n compétiteurs devant avancer de m cases.
La probabilité pour i de gagner est la probabilité de tirer i et d'être dans une situation gagnante (c'est à dire i a été tiré m-1 fois, et tous les autres ont été tirés au maximum m-1 fois).
La probabilité d'être dans une situation gagnante est la somme des probabilités de toutes les situations gagnantes.
La probabilité d'une situation gagnante est la somme des probabilités des tirages qui peuvent à mener.
Un tirage est un arrangement distinct de résultats d'épreuves.
La probabilité d'un tirage est le produit des probabilités de ses épreuves successives.

Soit P le vecteur des probabilités individuelles de succès d'épreuve.
Soit noté N le contingent d'une situation (le nombre de tirages effectués).
Le nombre de tirages menant à une situation est ntirages(N) = somme(N)!/produit(N), c'est le nombre d'arrangements non équivalents d'une situation.
La probabilité d'une situation de contingent N est p_situation(N) = produit(P^N)*ntirages(N).

Soit EN l'ensemble des situations gagnantes
La probabilité pour i de gagner est
p_i*(somme(N dans EN, p_situation(N)))

J'ai bon ?