[Algo] Une énigme très très complexe

[Olivman]

Aujourd'hui, après la publication de mon premier tutoriel, tout pourri, tout nul, dont j'ai pas encore mis à jour la présentation, je suis d'humeur à (un peu) me la péter. Donc, je vais vous donner l'énigme que mon prof de maths de seconde m'a donné. Enfin, donné, il s'attendait pas à ce qu'on la résolve, mais j'avais pas mieux à faire (ce prof de maths est assez barbant).

Cette énigme n'est pas une énigme classique, dans le sens où si vous connaissez la réponse, vous savez tout, ou une énigme bateau tirée par les cheveux, ce n'est pas non plus une équation. C'est de la logique pure : c'est une énigme algorithmique.


L'énigme

On place sur une grille de 12x5 cases des pions, un par colonne, soit 12 pions.
On prend deux dés (des D6).
On décide que le pion numéro 1 (1ère colonne) avancera d'une case quand on tirera 1 aux dés. Autant dire qu'il n'est pas près d'avancer :noel:
On décide que le pion numéro 2 (2nde colonne) avancera d'une case quand on tirera 2 aux dés. Lui non plus, il ira pas très vite.
Et ainsi de suite, chaque pion avance sur la prochaine ligne quand le numéro de sa colonne est tiré.
Je répète pour éviter les confusions : un pion ne peut avancer que d'UNE case.

Quelles sont les chances de chaque pion d'arriver premier ?
EDIT : il paraît que je ne suis pas assez clair, donc, je précise : quelles sont les chances de chaque pion d'être le premier à avoir franchi les 5 cases ? Autrement dit, d'être le premier dont le nombre est tiré 5 fois ?



D'une part, on sait que le pion 1 n'avancera jamais (essayez donc de faire 1 avec deux D6 ^^). On sait que les pions 2 et 12 seront les plus "lents", et que le 7 sera le plus rapide, PAS LA PEINE D'INDIQUER CE QUI PRÉCÈDE.
Ce que je veux, c'est
- Les chances de chaque pion de gagner
- Comment vous avez trouvé (donc ceux qui pensent à Python/Java/C++, n'y pensez plus)
- Pour les plus courageux, les chances de chacun de gagner si leur nombre de cases à parcourir est égal à 3*n, en sachant que n est le numéro de leur colonne.

Pas la peine non plus de tenter un tableau de signes, il faudrait envisager environ 5 milliards de possibilités (algo en O(N1^N2), où N1 est le nombre de pièces et N2 le nombre de cases à franchir ):noel:
Et oui, j'ai (je crois) trouvé la solution de cette énigme. Je pense la poster en page 2.
La solution est en O(N^2), ce qui n'est pas mal du tout. Mais elle est atrocement horriblement terriblement dégueulacement difficile à trouver. Bon, j'en fait peut-être un petit peu trop.

Néanmoins, sachez que si vous la trouvez et la montrez à vos proches, vous passerez pour l'empereur des maths que vous êtes (notez ma façon subtile et détournée de me la péter).

Je vous donnerai des indices pour trouver la solution si vous avez du mal. De mon côté, étant un débutant programmeur génial en maths fan de Redstone, de LBP-2, et autres ... il m'a fallu à peu près 2 heures plus ou moins entrecoupées pour trouver la solution, étant parti dès le début sur la bonne piste. Maintenant je vous dis : bonne chance
Et persévérez, si vous y arrivez c'est que vous ferez fureur en tant que programmeurs.


EDIT : pour vous aider et pour éviter d'avoir une centaine de réponses qui pensent que trouver les probabilités de chute des dés est le plus difficile, je vous les donne :
- Chiffre 1 : 0 chance
- Chiffre 2 : 1 chance sur 36
- Chiffre 3 : 2 chances sur 36
- Chiffre 4 : 3 chances sur 36
- Chiffre 5 : 4 chances sur 36
- Chiffre 6 : 5 chances sur 36
- Chiffre 7 : 6 chances sur 36
- Chiffre 8 : 5 chances sur 36
- Chiffre 9 : 4 chances sur 36
- Chiffre 10 : 3 chances sur 36
- Chiffre 11 : 2 chances sur 36
- Chiffre 12 : 1 chance sur 36

Et sachez que X^Y signifie X puisssance Y.

EDIT : je change un peu le titre ^^

 

[draentor]

RE: [Algo] L'énigme la plus complexe que j'ai résolu

1/12 chances de gagner par pions, je pense. Vu que il y a 12 faces en tout, 12 possibilités, donc 1/12 chances ^^

Je dis ça, parce que demain, j'ai un bac blanc de maths, probabilités y compris donc....

 

[Olivman]

RE: [Algo] L'énigme la plus complexe que j'ai résolu

Oulah, je veux pas dire, t'es sûr que t'as révisé ?
Ou c'est parce que t'es crevé, tu devrais aller te coucher (bon j'arrête de t'enfoncer).

D'une part, les douze nombres n'ont pas autant de chances de tomber les uns que les autres :
- Le 1 ne tombera jamais, vu que le minimum sur un D6 est de 1, et que 1+1 = 2>1;
- Le 2 et le 12 ne tomberont pas souvent, vu qu'il faut faire deux fois le même nombre pour les avoir, alors qu'il y a 6 combinaisons différentes qui donnent 7, lequel a donc 6 fois plus de chances de tomber

D'autre part, les chances de gagner ne sont pas forcément exactes aux chances d'avancer. Puisque, une fois qu'on avance, nos chances de gagner sont différentes, et elles sont encore différentes si tel ou tel gagne, etc ...

Ne croyez pas qu'il y a une solution toute bête, l'algorithme de l'arbre de possibilités est un algo en O( ( (nombre pièces)^nombre de cases par pièces)^2 )*2 ). L'zlgo le plus simple que j'aie trouvé est en O( nombre pièces ^2 ).
Si vous voulez le trouver (et donc pouvoir prétendre être meilleur algorithmicien que moi), il va falloir chercher dur ^^

 

[draentor]

RE: [Algo] L'énigme la plus complexe que j'ai résolu

Oh oui xD Même nos trucs en Terminale sont pas si compliqués... M'enfin, les nombres complexes, intégrales, Logarythme népérien, exponetielle, limites, dérivation, primitives ont fini de m'assomer... Allez, je me détends sur Minecraft !

 

[Mengard]

RE: [Algo] L'énigme la plus complexe que j'ai résolu

Bon alors allons-y
2 dés de 6,
On a 36 possibilités si on compte que (1;6) est différent de (6;1)

Chance d'avoir 2 : (1;1) soit une possibilité
Chance d'avoir 3 : (1;2) / (2;1) deux possibilités
Chance d'avoir 4 : (1;3) / (2;2) / (3;1) trois possibilités
Chance d'avoir 5 : (1;4) / (2;3) / (3;2) / (4;1) quatre possibilités
Chance d'avoir 6 : (1;5) / (2;4) / (3;3) / (4;2) / (5;1) cinq possibilités
Chance d'avoir 7 : ... 6 possibilités (oui à la base je voulais vous faire un truc simple pour vous expliquer clairement, mais là j'ai la flemme alors je synthétise)
Ensuite c'est décroissant, pour 8 les mêmes chances que 6, pour 9 les mêmes chances que 5, ... ce qui nous fait un total de 6+(5+4+3+2+1)x2 soit 36 possibilités, et oui, comme dit plus haut
Ensuite on reprend comme avant qu'on divise par le nombre total de possibilité:
Chance d'avoir 2 ou 12: 1 chance sur 36 : 1/36 : 2,7778%
Chance d'avoir 3 ou 11: 2 chances sur 36 : 1/18 : 5,5556%
Chance d'avoir 4 ou 10: 3 chances sur 36 : 1/12 : 8,3333%
Chance d'avoir 5 ou 9 : 4 chances sur 36 : 1/8 : 11,1111%
Chance d'avoir 6 ou 8 : 5 chances sur 36 : 5/36 : 13,8889%
Chance d'avoir 7 : 6 chances sur 36 : 1/6 : 16,6667%

Et comme il faut avancer de 5 cases, il faut avancer 5x, donc gagner 5x, donc hop, chance^5 (j'vois pas pourquoi faut mettre des x2 et des ^2 en plus en fait :/)

 

[Olivman]

RE: [Algo] L'énigme la plus complexe que j'ai résolu

En fait, je crois que ça aurait dû rentrer dans la catégorie "Pratiquement tout le monde le sait, pas la peine de l'écrire".

Et non, ton raisonnement ne tiens pas.

En gros, ton idée, c'est que les chances de gagner d'un pion sont "chance de gagner = chance d'avancer puissance nombre de cases" ? Ce raisonnement ne tient pas. Parce que dans ce cas, deux pions avec chacun une chance sur deux d'avancer et devant avancer de deux case auraient chacun 0.5^2 = 0.25 de gagner, or ils doivent tout le temps avoir 0.5 chances de gagner.

Si c'est trop simple, cherchez l'erreur, je vous ai dit que c'était un algorithme en O(N^2) le plus simple et que j'avais bossé une heure et demie pour le trouver (si après ça je passe pas en S ...).

 

[Mengard]

RE: [Algo] L'énigme la plus complexe que j'ai résolu

Bon, moi à défaut d'être en S, je suis en I(nformatique) alors go python (pas besoin de plus) pour faire un programme simulant ta situation quelques millions de fois et voyons les pourcentages

 

[Olivman]

RE: [Algo] L'énigme la plus complexe que j'ai résolu

Ah, oui évidemment, tu peux faire un programme simulant l'algo de base, mais où est l'intelligence du mec qui trouve (parce que c'est pas un truc dur à coder franchement). Et nul besoin de suivre des cours de S (évidemment, si vous êtes littéraires), puisque j'ai moi-même trouvé la solution en moins d'une journée (donc si vous y réfléchissez un moi ou deux, statistiquement, vous ne pouvez pas trouver) et que je suis en seconde. Donc il devrait y en avoir qui trouvent ^^.

 

[Mengard]

RE: [Algo] L'énigme la plus complexe que j'ai résolu

PS: j'ai jamais pensé que les probabilités de chute de dée sont les plus dures à calculer, au contraire, c'est le plus simple, pas de factorielle, rien, juste compter, c'est juste laborieux de tout réécrire alors que ça coule de source

Je vais me pencher plus sérieusement sur le problème en ce moment, j'ai quand même rien à faire.

 

[Olip96]

RE: [Algo] L'énigme la plus complexe que j'ai résolu

Techniquement, ce n'est pas une énigme mais plutôt un problème mathématique ...

Enfin bref, j'suis pas là pour corriger tout le monde donc bon.