Il faut passer les premiers.

[Waax22951]

Bonjour,
Je me posais une question sur un exercice du concours général (2013), sur l'exercice suivant:

Exercice:
Pour faire une réussite, Sisyphe a dessiné au sol 106 cases numérotées de 0 à 105, et il dispose d'un jeton ainsi que d'un dé à six face (équilibré).
Sisyphe commence la réussite en posant le jeton sur la case 0. Il fait ensuite une série de lancers du dé ;
lorsque le dé affiche la valeur k, il avance le jeton de k cases et :
– s’il atteint ou dépasse la case numéro 100, Sisyphe a gagné ;
– s’il arrive à une case dont le numéro est un nombre premier inférieur à 100, Sisyphe a perdu ;
– dans les autres cas, Sisyphe relance le dé et continue la réussite.

Dans la suite du problème, Sisyphe ne recommence plus la réussite s’il perd.
Soit X la variable aléatoire représentant la position du jeton à la fin de la réussite.
On note P(X = k) la probabilité de l’événement X= k.

Je me demandais si on pouvais déterminer la valeur de P(X=k) en fonction de k, sans algorithme (c'est ce que demande l'exercice sur une question, donc je sais que c'est faisable..)

Je ne sais pas si ça peut aider, mais j'ai remarqué que si on raisonne uniquement en terme de déplacement du jeton, on a pour tout entier k et k' tels que k<k':


Merci d'avance ! :lol3:

[Doraki]

Ta propriété me paraît bizarre, puisque X ne peut valoir que 100,101,...,105

Si on s'arrête à partir de la case n, la loi de (X-n) converge vers une loi (que j'ai la flemme d'expliciter), et elle le fait exponentiellement.

Si je me gourre pas ces probabilités se lisent sur la première colonne de la matrice

1/6 1 0 0 0 0
1/6 0 1 0 0 0
1/6 0 0 1 0 0
1/6 0 0 0 1 0
1/6 0 0 0 0 1
1/6 0 0 0 0 0

élevée à la puissance n

Donc tu peux essayer de la diagonaliser pour commencer.

[Waax22951]

Merci pour ton message ! :lol3:

Ta propriété me paraît bizarre, puisque X ne peut valoir que 100,101,...,105

Je ne comprends pas ce que tu veux dire: X peut très bien valoir 2, par exemple, il s'agit de l'évènement "Le jeton est sur la case 2". Après pour la propriété il s'agit juste de dire que calculer la probabilité d'atteindre la case k' en partant de la case k est la même que d'atteindre la case k'-k en partant de 0: par exemple, on a exactement une chance sur 6 d'atteindre la case 9 si on est sur la case 8, car il faut nécessairement faire un 1 avec le dé..

Je ne comprends pas comment on peut en déduire que ces probabilités se lisent sur la matrice que tu as présenté. Pour ce qui est de diagonaliser, on ne l'a pas vu en cours, donc je ne saurais même pas te dire si cette matrice est diagonalisable (je suppose que oui..).

Merci tout de même pour ces infos ! :we:

PS: je ne suis pas sûr de ce que je dis, mais je me demande une chose: si (X-n) converge vers une loi, il faut que n soit relativement grand, et pourtant, ce n'est pas forcément le cas, non ? (On peut avoir par exemple n=2)

[Doraki]

Oh zut j'avais mal compris j'croyais qu'on ignorait la clause "il s'arrête quand il tombe sur un nombre premier"

Du coup ça m'étonnerait vraiment beaucoup que tu trouves un moyen simple calculer les probabilités en question, et tu peux effacer ce que j'ai dit

X est la v.a. qui indique la case où est le jeton à la fin de la réussite, une fois qu'il a gagné ou perdu.
Ca ne parle pas des cases visitées en cours de route.

Si tu veux parler de l'événement "le jeton est passé par la case k" il faut l'appeler autre chose, genre Yk et pas X=k

[Skullkid]

En effet je ne pense pas qu'il y ait de moyen simple de calculer les probas. Le formalisme utilisé par Doraki dans son post précédent est adapté, sauf qu'il faut considérer une matrice 106*106 et l'élever à la puissance 76, donc c'est assez lourd à faire à la main :)

Mais l'ordi le fait rapidement et les résultats sont assez intéressants, on peut voir par exemple que la probabilité de gagner est seulement d'environ 0.035% et que la probabilité de perdre avant d'atteindre la case 30 est supérieure à 95%.

[beagle]

...la probabilité de gagner est seulement d'environ 0.035% et que la probabilité de perdre avant d'atteindre la case 30 est supérieure à 95%.

estimation gain 100:
(3/4)^28 = 0,032%

estimation gain à 30:
(2/3)^8= 0.039 = 3,9%

[zygomatique]

salut

pour résumer Trucmuche lance le dé tant qu'il ne dépasse pas 100 (au sens large) et qu'il ne tombe pas sur un nombre premier p auquel cas il a perdu


2 = 2 = 1 + 1 donc P(X = 2) = 1/6 + (1/6)²

3 = 3 = 1 + 2 donc P(X = 3) = 1/6 + (1/6)^2

5 = 5 = 1 + 4 = 4 + 1 donc P(X = 5) = 1/6 + 2(1/6)^2

7 = 1 + 6 = 4 + 3 = 6 + 1 = 1 + 3 + 3 = 4 + 2 + 1 donc P(X = 7) = 3(1/6)^2 + 2(1/6)^3



et évidemment on ne peut pas écrire 3 = 1 + 1 + 1 puisque avec 1 + 1 = 2 on tombe sur un nombre premier donc on s'arrête ...

donc le problème est de compter pour tout nombre premier p le nombre de sommes ordonnées de n (variable) entiers de [[1, 6]] telles que

et pour tout k = 100 ...

ça me semble bien compliqué ....

[Waax22951]

Bonjour,
Désolé, j'avais aussi mal lu l'énoncé: je n'avais pas vu que la variable aléatoire X comptait le numéro de la case où il s'arrête, et non où il passe. Du coup ma remarque n'est pas vraiment utile..!
J'avoue ne pas avoir encore fait l'algorithme, mais je me doutais que la probabilité de gain était très faible..!
Zygomatique: C'est vrai que ça semble assez compliqué, mais penses-tu que l'on puisse trouver une réponse avec les outils de dénombrement simples ? Car cela m'intéresserait..!

Bon après-midi !

[nodjim]

Petite correction au calcul de beagle:
le nombre moyen par coup est 3,5. Pour parcourir les 97 cases (au dela de 97, il gagne) il faut 97/3,5 coups en moyenne.
le pourcentage de cases autorisées est de (97-25)/97=72/97
Le taux de réussite attendu serait alors de (72/97)^(97/3,5)=2,58..*10^-4. C'est plus faible que le 3,5*10-4 de la simulation de Skullkid. La différence est assez marquée. Pourtant, on pourrait penser que le sévère barrage 2,3,5,7 dégrade le taux de réussite.

[nodjim]

Rien que pour passer 6 et réussir le coup d'après, on tombe déja à moins de 10% de réussite.

[nodjim]

On peut faire quelques beaux problèmes sur le sujet. Par exemple, si le pion est au 90 quelles sont ses chances de sauter par dessus le 97 ?

[zygomatique]

pour p premier on peut continuer assez aisément (à la main !!) à calculer P(X = p) pour p = 11, 13, 17 et 19 ....

au delà ça devient ... pénible .... mais faisable .... puisqu'il n'y a pas plus de trois nombres premiers par dizaine au maximum ...

on peut aussi remarquer qu'il faut au moins p/6 lancers pour arriver à p ...


sinon on peut effectivement effectuer une approche algorithmique type Monte-Carlo ....

[Waax22951]

pour p premier on peut continuer assez aisément (à la main !!) à calculer P(X = p) pour p = 11, 13, 17 et 19 ....

au delà ça devient ... pénible .... mais faisable .... puisqu'il n'y a pas plus de trois nombres premiers par dizaine au maximum ...

on peut aussi remarquer qu'il faut au moins p/6 lancers pour arriver à p ...


sinon on peut effectivement effectuer une approche algorithmique type Monte-Carlo ....

D'ailleurs, j'y pense: pensez-vous qu'un algorithme du type de Monte-Carlo peut suffire comme réponse lorsque, au concours général, ils demandent un algorithme pour connaître P(X=k) ?
Ou faut-il un algorithme qui détermine toutes les possibilité ?

[zygomatique]

je pense qu'un algorithme type Monte-Carlo avec un nombre conséquent d'essais (disons 10000) devrait donner une réponse raisonnable ....

comme il a été dit plus haut avec 8 nombres premiers parmi les 20 premiers nombres dépasser les 20 doit être exceptionnel ....

maintenant comme je l'ai dit calculer à la main P(X = p} pour p = 11, 13, 17, 19 n'est guère compliqué ... non plus par informatique d'ailleurs qui permettrait de calculer la valeur exacte de P(X = p)

surtout quand il faut au moins 2 lancers et que le premier ne peut être premier .... et que même le nombre de lancers est inférieur à p - 1 (majoration très grossière) au maximum (on peut même penser à ce qu'il soit inférieur à p/3 en gros)

allez je te donne gratos pour 11

11 = 6 + 5 (en deux coups)

11 = 1 + 5 + 5 = 4 + 2 + 5 = 4 + 4 + 3 = 4 + 5 + 2 = 4 + 6 + 1 = 6 + 2 + 3 = 6 + 3 + 2 = 6 + 4 + 1 (en trois coups)

11 = 1 + 3 + 2 + 5 = 1 + 5 + 2 + 3 = 1 + 5 + 2 + 3= 1 + 5 + 3 + 2 = 1 + 5 + 4 + 1 (en quatre coups)

11 = 1 + 3 + 2 + 2 + 3 = 1 + 3 + 2 + 3 + 2 = 1 + 3 + 2 + 3 + 1 + 1 = 1 + 3 + 5 + 1 + 1 = 1 + 5 + 2 + 1 + 2 = 1 + 5 + 2 + 2 + 1 = 1 + 5 + 3 + 1 + 1 = 4 + 2 + 2 + 1 + 2 = 4 + 2 + 3 + 1 + 1 = 4 + 4 + 1 + 1 + 1 (en cinq coups)


11 = 1 + 3 + 2 + 2 + 1 + 2 = 1 + 3 + 2 + 2 + 2 + 1 = 1 + 5 + 2 + 1 + 1 + 1 = ....
11 = 4 + ....


bon j'ai du en oublier ....

mais ça se programme aisément (je pense) car à chaque fois qu'on a écrit une suite partielle alors pour ajouter le terme suivant il en faut pas obtenir un premier inférieur à p ce qui est une contrainte forte ....

d'ailleurs on voit déjà que le premier coups est 1, 4 ou 6

avec 1 le deuxième coup ne peut pas être 1, 2, 4, 6 (donc plus que deux possibilités)

avec 4 le deuxième coup ne peut pas être 1 ou 3

avec 6 le deuxième coup ne peut pas être 1 ou 5

donc la probabilité de lancer une troisième fois le dé est 1/6 * 1/3 + 2 * 1/6 * 2/3 = 5/18

on a donc déjà moins d'une chance sur trois de lancer le dé au moins trois fois ....

[nodjim]

Le calcul exact de la proba (avec un simple tableur, ça se fait en quelques minutes) est de 0,000344912.....
Comment m'y suis je pris ?

[zygomatique]

de la proba de quoi déjà ? de gagner ?

oui comment t'y prends-tu ?

[nodjim]

Je commence par faire une colonne de 102 à 0. Sur la colonne suivante, je donne les probas de réussite: pour 102 à 98 :1; pour 97: rien. Pour 96 et tous les suivants: la moyenne des 6 nombres au dessus. Ne reste plus ensuite qu'à supprimer les formules de la seconde colonne face aux nombres premiers. Le résultat final apparait ligne 0.
Un extrait ci dessous:

102 1
101 1
100 1
99 1
98 1
97
96 0,833333333
95 0,805555556
94 0,773148148
93 0,735339506
92 0,691229424
91 0,639767661
90 0,746395605
89
88 0,597646724
87 0,568396487
86 0,54057265
85 0,515463188
84 0,494745776
83
82 0,452804137
81 0,428663706
80 0,405374909
79
78 0,296931421
77 0,263962362
76 0,307956089
75 0,283814748
74 0,259673255
73
72 0,235389646
71
70 0,181138956
69 0,160002768
68 0,139367438
67
66 0,119316468
65 0,099970938
64 0,116632761
63 0,105881729
62 0,096861556
61
60 0,089777242
59
58 0,068192215
57 0,06011879
56 0,052491634
55 0,045096647
54 0,052612755
53
52 0,046418673
51 0,04278975
50 0,039901576
49 0,037803233
48 0,036587665
47
46 0,033916816
45 0,031833173
44 0,030007077
43
42 0,022057455
41
40 0,019635754
39 0,017255577
38 0,014825977
37
36 0,012295794
35 0,01066885
34 0,012446992
33 0,011248865
32 0,010247746
31
30 0,009484708
29
28 0,007238052
27 0,006369895
26 0,005556734
25 0,004774898
24 0,005570714
23
22 0,004918382
21 0,004531771
20 0,004225416
19
18 0,003207714
17
16 0,002813881
15 0,00246313
14 0,002118357
13
12 0,00176718
11
10 0,001527091
9 0,001312626
8 0,001120876
7
6 0,000954629
5
4 0,000819204
3
2
1 0,000295639
0 0,000344912

[zygomatique]

ha oui bien vu .... en partant de la fin !!!!

[nodjim]

Une curiosité: on a moins de chance d'arriver au bout en partant de 1 qu'en partant de 0. Ce n'est pas le seul cas (voir 24-25;34-35;54-55;64-65;...)

[zygomatique]

pas étonnant :: en partant de 0 on a une chance sur deux de tomber sur un premier et deux chances sur 3 en partant de 1 ...