Bonjour,

Petite animation sympathique.

Doit on réduire les nombre de coups à 4 ?

En supposant qu'on se  limite à  4  lancements:

Bonsoir
En 3 lancers je trouve 7 parcours possibles.
En 4 lancers j'en trouve 40.
Attention on ne peut pas faire un retour en arrière. 1 suivi de 5 ou l'inverse on est éliminé.
Il y a "beaucoup" de parcours en 5, 6, 7, 8 et 9 lancers.

Bonjour,
Tu pourrais fixer le nombre de coups pour arriver au but.
Je pense qu'il n'est pas utile de dépasser 5,pour éviter de tourner en
rond.
Personnellement,je n'ai pas assez éliminé d'impossibles pou 4.
Je regarderai plus tard avec la méthode qui part de l'idée que chaque
chiffres du parcours forme un nombre avec des interdis genre 11ab 12ab ,ab44,etc....
Petite remarque pour les  7 parcours en  3 : le chiffre 6 peut être utilisé 3 fois
pour chacun ce qui donne 21 parcours en 4 ce qui porterait à 61 le total.

Bonjour
Comme le 6 n'intervient pas pour les déplacements je n'en ai pas tenu compte (c'est comme si on avait un dé à 5 faces). Quand je dis qu'il existe 7 parcours possibles en 3 lancers, c'est 3 lancers minimum.
Les voici : 234  243  324  333  342  423  432

Pour calculer la probabilité d'arriver en A il faut cumuler toutes les probas de tous les parcours possibles arrivant en A.
En 9 lancers il n'y a que 2 parcours possibles qui sont 135531135 et son symétrique 531135531 (pour avoir un symétrique vertical il suffit de prendre pour chaque chiffre son complément à 6).

Pour chaque chiffre j'ai considéré que la proba de l'obtenir est 1/5 (dé à 5 faces).
La proba d'arriver en A en 9 lancers est donc de :
2 x (1/5)^9

Salut,
Merci pour ce petit problème

J'ai résolu le problème en brute force à l'aide de Python :

 Cliquez pour afficher

from collections import defaultdict
from fractions import Fraction

def solve(h=3,l=1):
   paths = defaultdict(set)
   stack = [((0,0),(0,))]
   while stack:
      (x,y),path = stack.pop()
      if (x,y) == (0,h):
         paths[len(path)].add(path)
         continue
      if x > -l and path[-1] != 5:
         stack.append(((x-1,y),path+(1,)))
      if x > -l and y < h:
         stack.append(((x-1,y+1),path+(2,)))
      if y < h:
         stack.append(((x,y+1),path+(3,)))
      if x < l and y < h:
         stack.append(((x+1,y+1),path+(4,)))
      if x < l and path[-1] != 1:
         stack.append(((x+1,y),path+(5,)))
   p = sum(Fraction(len(paths[l]))/Fraction(5**(l-1)) for l in paths)
   return p, paths

 Cliquez pour afficher

  7 chemins de longueur 3
 40 chemins de longueur 4
 92 chemins de longueur 5
112 chemins de longueur 6
 70 chemins de longueur 7
 20 chemins de longueur 8
  2 chemins de longueur 9

Ce qui donne une probabilité de 307727:5⁹ 15.76% d'arriver à l'arrivée.

J'étais sûr que Littlefox serait dans le coup

Sauf que en simulant le jeu j'obtiens des résultats trop différents. Où est l'erreur?

Voici le simulateur :

 Cliquez pour afficher

from random import randint
def play(h=3,l=1):
   x,y,lastMove = 0,0,0
   while (x,y) != (0,h):
      dice = randint(1,6)
      if dice == 1:
         if lastMove == 5:
            return False
         x -= 1
      elif dice == 2:
         x -= 1
         y += 1
      elif dice == 3:
         y += 1
      elif dice == 4:
         x += 1
         y += 1
      elif dice == 5:
         if lastMove == 1:
            return False
      if dice != 6:
         lastMove = dice
      if x < -l or x > l or y > h:
         return False
   return True

 Cliquez pour afficher

J'obtiens que la probabilité d'arriver en A est avec grande confiance (dix fois 1 million de partie) supérieure à 17.2%.

Bonjour

Voilà un problème qu'il est intéressant... je propose une solution sans tenir compte de l'élimination quand on revient sur ses pas... ce qui complique bien les choses et je n'ai pas de solution pour l'instant au problème tel qu'il est posé... mais ce que je propose donnera peut-être des idées à certains !

 Cliquez pour afficher

je note p_i la probabilité d'arriver en A à partir de la case où il est écrit. Pour des raisons de symétrie du problème, les colonnes gauches et droites sont égales.



on cherche donc p₆ et je note

par convention puisque c'est l'arrivée, p₀=1

et on remarquera que d'une case 7 on a qu'une possibilité pour aboutir... ou alors tirer un 6 et on reste sur la même case

donc



ce qui donne

et donc  

pour i1, en analysant les 6 possibilités d'une case "paire" :



et pour une case "impaire" :



en arrangeant cela avec les matrices   et
on obtient



et finalement

et une probabilité d'arriver en A de

sauf erreur dans mes calculs !

maintenant il faut éliminer les chemins où il y a eu une série 151 ou 515 ...

je ne comprends pas que vous "éliminiez" le cas "6" car il ne stoppe pas le jeu mais le ré-initialise là où il en était.... vous ne tenez pas compte des possibilités à 31416 lancers... quand on a très souvent lancé un 6 !

J'ai trouvé mon erreur dans ma simulation j'ai oublié d'aller à droite quand je fais 5
Après correction j'obtiens 15.753% avec un sigma de 0.25% ce qui est beaucoup plus proche

@matheuxmatou
J'aime bien ton approche même si j'ai du mal à suivre d'où viennent A et B aussi, si tu as besoin de je l'aurais mis dans (pour moi devrait avoir 4 composantes. Aussi, c'est et non . Non?

En simulant sans élimination quand on revient sur ses pas j'obtiens des résultats cohérents avec ta probabilité (195102 succès sur un million). Ça m'a l'air juste .

Pour éliminer quand on revient sur ses pas on peut combiner deux mouvements. En effet comme on ne peut pas redescendre, la seule manière de revenir sur ses pas est de faire 15 ou 51.

On peut éliminer le 6 si on cherche la probabilité d'arriver en A. En effet faire 6 est équivalent à annuler le lancer de dé et le relancer. Ce qui est lui-même équivalent à avoir un dé à 5 faces.
Par contre si on cherche à connaitre l'espérance du nombre de lancer pour arriver à A alors on ne peut pas éliminer le 6.

Bravi LittleFox. Je n'ai pas su mettre en programme. J'avais d'abord essayé de voir tous les cas mais c'est vraiment trop long. Donc je suis parti de case en case en faisant attention à ne pas revenir sur ses pas et j'ai comme toi.
Si l'on peut "revenir en arrière" comme le suggère matheuxmatou le nombre de coup peut devenir "infini". J'avais vite laissé tomber.
LittleFox, ton simulateur est loin du résultat. Y aurait-il une faille dans ton programme ?

Bravo et non bravi (quoi que ce pourrait être un pluriel italien)

LittleFox, dans ton simulateur, fais comme si on avait un dé à 5 faces pour voir.

LittleFox je n'avais pas lu ton dernier message quand j'ai rédigé mes 3 précédents messages.

LittleFox
ben oui évidemment... j'étais parti sur une numérotation différente au début et me suis emmêlé les pinceaux

dans le début de la démo, remplacer les p₇ par des p¹

merci

derny
J'ai vu
Dans mon simulateur j'ai essayé avec un dé à 5 faces. Comme prévu, ça ne change rien.
Ça changerait si on regardait la longueur moyenne du chemin.

matheuxmatou
En reprenant tes notations, inclure l'impossibilité de revenir en arrière, n'est pas difficile :

En enlevant le coup 6, au pire on fait deux mouvements latéraux avant de monter. Et dans ces mouvements on va toujours du même côté. Ce qui donne :








On obtient bien

Finalement pas besoin de x à 4 éléments

LittleFox
je ne comprends toujours pas "en enlevant le coup 6" ... quand tu calcules p₁ pour trouver 1/5, tu tiens bien compte du "coup 6" qui est obtenu avec une proba de 1/6 et débouche ensuite sur p₁

et d'autre part, quand tu repars d'une case, il faut aussi connaitre le coup précédent pour savoir si on ne reviens pas sur ses pas ... ce n'est pas seulement "les deux suivants" qui comptent...

je ne comprends pas tes formules de récurrence.

@matheuxmatou
Pour calculer la proba avec ou sans le "coup 6" de p₁ on obtient bien la même chose : 1/5.

Quelle est la probabilité à l'infini d'avoir lancé 3 si quand on fait 6 on relance sinon on s'arrête?
On a p  = 1/6 (on a fait 3) + 1/6p (on a fait 6 donc on recommence comme s'il ne s'était rien passé). Donc p(1-1/6) = 1/6, donc p5/6 = 1/6, donc p = 1/6*6/5 = 1/5. Tout comme si on avait lancé un dé à 5 faces : p = 1/5 (on a fait 3)

De la même façon, dans tes calculs, tu as :


Pour mes formules de récurrences, prenons par exemple p₃ à gauche.
On peut :
(- Lancer 6 pour rester sur place)
- Lancer 3 pour aller en p₁
- Lancer 4 pour aller en p₀
- Lancer 5 pour aller en p₂ mais de là on ne peut que :
   (- Lancer 6 pour rester sur place)
   - Lancer 2 pour aller en p₁
   - Lancer 3 pour aller en p₀
   - Lancer 4 pour aller en p₁
   - Lancer 5 pour aller en p₃ mais de là on ne peut que :
      (- Lancer 6 pour rester sur place)
      - Lancer 2 pour aller en p₀
      - Lancer 3 pour aller en p₁

Vu qu'on ne peut pas redescendre, juste après un coup qui monte on est sûr de ne pas revenir en arrière et on peut s'arrêter

Soit w₅ la probabilité d'arriver en A en partant de p₃ et en faisant au premier jet 5 et w₅₅ la probabilité en faisant deux 5.

On a :







D'où mes coefficients 31 et 36. Note que l'on peut sauter les deux premières égalités dans les 3 équations si on fait comme si on avait un dé à 5 faces.

On fait la même chose pour p₂ pour obtenir

LittleFox

quand tu dis :
" Lancer 5 pour aller en p₂ "
à la 4eme ligne de ton raiusonnement... d'accord, mais à condition que le coup d'avant on ne vienne pas de p₂ avec un "1" ...

Toute l'idée de mon raisonnement c'est d'éliminer les lancers '1' et '5'.

En fait je transforme le problème :

P(x='1') = 1/6, 
P(x='2') = 1/6,
P(x='3') = 1/6,
P(x='4') = 1/6,
P(x='5') = 1/6,
P(x='6') = 1/6,
retour interdit

P(x='1') = 1/5, 
P(x='2') = 1/5,
P(x='3') = 1/5,
P(x='4') = 1/5,
P(x='5') = 1/5,
retour interdit

P(x='12') = 1/25, 
P(x='13') = 1/25, 
P(x='14') = 1/25, 
P(x='113') = 1/125, 
P(x='114') = 1/125, 
P(x='2') = 1/5,
P(x='3') = 1/5,
P(x='4') = 1/5,
P(x='52') = 1/25,
P(x='53') = 1/25,
P(x='54') = 1/25,
P(x='552') = 1/125,
P(x='553') = 1/125,
P(x='éliminé') = 2/25 + 6/125 ('15', '51', '111', '112', '115', '551', '554', '555')

LittleFox je confirme

J'ai procédé différemment, en calculant, partant de A, les probas d'aboutir pour chaque case (qui est aussi la proba d'aboutir quand on vient de la ligne d'en dessous). Les arbres vont vite à faire car pour chaque "couche" on utilise les probas calculées de la ligne du dessus.

et j'ai trouvé :