![](/img/vague-bas-gauche.png) |
#1 - 29-07-2015 10:47:27
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1958
Prisonniers, ampoules, et durée de eju + Indices
Bonjour !
Considérons l'énoncé suivant, qui se trouve aussi ici : http://www.prise2tete.fr/forum/viewtopic.php?id=4234
On va faire plus général : on a N prisonniers. Chaque jour, un prisonnier passe dans une pièce où se trouve une ampoule et un interrupteur (auquel personne n'a touché depuis le précédent passage). Le prisonnier est libre de faire ce qu'il veut de l'interrupteur. L'expérience s'arrête quand un prisonnier peut affirmer : "tout le monde est passé dans la pièce".
On prendra la méthode de résolution présentée dans le topic sus-mentionné. Je ne la ramène pas ici pour laisser le plaisir de la trouver à ceux qui ne la connaissent pas.
La question est la suivante : en fonction de N, combien de jours en moyenne durera l'expérience ?
La case réponse valide le nombre moyen de jours pour 1 million de prisonniers, avec 2 chiffres après la virgule
Edit : Allez, un indice pour mieux démarrer Spoiler : [Afficher le message] (...)* signifie "un parmi la liste, autant de fois qu'on veut" Pour 2 prisonniers A et B, la séquence "gagnante" est toujours: A (A)* B (B)* A
Pour 3 prisonniers A, B et C; elle sera toujours: A (A)* B (BC)* A (AB)* C (BC)* A
Pour 4, ça sera: A (A)* B (BCD)* A (AB)* C (BCD)* A (ABC)* D (BCD)* A
etc...
(autrement dit, le premier passe, puis on attend une personne qui n'est jamais passée, puis on attend le retour du premier, puis une personne qui n'est jamais passée, puis le retour du premier, ...)
Indice 2 : premiers résultats Spoiler : [Afficher le message] Pour N=2; il faut 5 jours en moyenne Pour N=3; il faut 11,5 jours en moyenne Pour N=4; il faut 20,333 jours en moyenne Pour N=5; il faut 31,41666 jours en moyenne Pour N=6; il faut 44,7 jours en moyenne Pour N=7; il faut 60,15 jours en moyenne Pour N=8; il faut 77,7428 jours en moyenne Pour N=9; il faut 97,460 jours en moyenne Pour N=10; il faut 119,289 jours en moyenne
#2 - 03-08-2015 12:07:58
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1958
Prisonniers, ampooules, et durée de jeu + Indices
Bon, ben le flop... C'était pas si compliqué pourtant.
Petit résultat préliminaire. On a un événement qui intervient avec une probabilité p; et X la variable aléatoire correspondant au nombre de fois où cet événement intervient d'affilée. P(X=z) = p^z * (1-p) On a E(X) = somme (z*p^z * (1-p), z>=0) = (1-p)*somme (z*p^z, z>=0) = (1-p)*p/(1-p)² = p/(1-p).
Revenons au problème. La méthode de résolution est la suivante : - un prisonnier qui passe en 1er allume la lumière quand elle est éteinte. - quand un prisonnier autre passe pour la première fois, il éteint la lumière si elle est allumée Lorsque le premier prisonnier aura allumé la lumière N fois, tout le monde sera passé.
Le premier passe : 1 passage Puis on attend qu'un autre prisonnier passe : le premier peut passer un certain nombre de fois, puis en viendra un autre qui sera le second. Puis le second passe : 1 passage Puis on attend que le 1er repasse : entre temps tous les autres peuvent passer un certain nombre de fois Puis le 3ème passe : 1 passage Puis on attend qu'un 3ème passe : le premier comme le second peuvent passer un certain nombre de fois avant etc...
(A-B)* signifie : un prisonnier dont le numéro (en ordre d'allumage) est compris entre A et B passe un certain nombre de fois.
Une séquence pour 2 prisonniers est alors: 1 (1-1)* 2 (2-2)* 1
Pour 3 prisonniers 1 (1-1)* 2 (2-3)* 1 (1-2)* 3 (2-3)* 1
Et pour N prisonniers 1 (1-1)* 2 (2-N)* 1 (1-2)* 3 (2-N)* 1 (1-3)* .... 1 (1-(N-1))* N (2-N)* 1 Ou encore 1 "(1-(j-1))* j (2-N)* 1" répété pour j allant de 2 à N
On a donc - (2N-1) passages "fixes" - (N-1) séries de passages de N-1 prisonniers parmi N - (N-1) séries de passage de j prisonniers parmi N, avec j allant de 1 à N-1
D'après le résultat préliminaire, une série de j prisonniers parmi N dure en moyenne (j/N)/(1-J/N) = j/(N-j) passages.
La durée moyenne du jeu est donc : 2N-1 + (N-1)*(N-1)/(N-N+1) + somme(j/(N-j), 1<=j<=N-1) = N² + somme(j/(N-j), 1<=j<=N-1)
La somme peut se transformer une une double somme sur i et j des 1/j avec 1<=j<=i<=N-1, et ensuite s'écrire avec des fonctions pompeuses à base de polygamma et autres joyeuseries, mais on peut tout aussi bien s’arrêter là : le jeu dure en moyenne N² + somme(j/(N-j), 1<=j<=N-1) Même avec un simple tableur, on peut sortir les résultats
Pour le jeu initial avec 100 prisonniers, la durée moyenne est donc de 10419 jours environ, soit un peu plus de 28 ans et demi... Et pour 1.000.000 de prisonniers, environ 1000013392726,72 jours soit a peu près 20% de l'age de l'univers
#3 - 03-08-2015 15:07:53
- Franky1103
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 3218
- Lieu: Luxembourg
prisonniers, ampouled, et durée de jeu + indices
Non... L’absence de réponses ne signifie pas un manque d’intérêt pour une énigme, certains ayant sûrement beaucoup cherché, mais…
C'était pas si compliqué pourtant.
… ben justement si, en tous cas pour moi, malgré les indices donnés.
#4 - 03-08-2015 17:00:26
- emmaenne
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 3073
- Lieu: Au sud du Nord
Prisoniners, ampoules, et durée de jeu + Indices
En fait, je ne comprends pas ces problèmes, ni ce que l'on cherche, ni la solution donnée. Désolé.
Dans le cadre de la quinzaine du beau langage, ne disez pas disez, disez dites. (Julos Beaucarne)
#5 - 03-08-2015 18:52:02
- Promath-
- Elite de Prise2Tete
- Enigmes résolues : 18
- Messages : 1416
- Lieu: Au fond de l'univers
Prisonniers, ampoules,, et durée de jeu + Indices
Je n'avais pas compris le problème, et généralement j'abandonne dans ce cas car c'est trop élevé pour moi, mais peut-être que je saurai le résoudre quand j'aurai fait 1-2 années de maths
Un promath- actif dans un forum actif
#6 - 03-08-2015 18:52:09
- Vasimolo
- Le pâtissier
- Enigmes résolues : 49
- Messages : 5,418E+3
Prisonniers ,ampoules, et durée de jeu + Indices
scarta a écrit:Bon, ben le flop...
Pourquoi ne pas être resté aux 100 prisonniers ? Je ne suis pas fan de probas , s'il faut en plus se farcir du tableur ...
Je dis ça je ne dis rien , on a tous eu une bonne dose de flops auxquels on n'a rien compris ![big_smile](img/smilies/big_smile.png)
La prochaine énigme sera la bonne ![smile](img/smilies/smile.png)
Vasimolo
#7 - 03-08-2015 18:53:17
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1958
Prisonniers, ampoules, et duurée de jeu + Indices
@Franky: je sais. Ceci dit, le problème n'est pas innocent. Souvent, quand il y a des posts liés à des calculs de probabilité / espérance / variance / écart-type / ..., on voit plus souvent du Python que des variables aléatoires ![smile](img/smilies/smile.png) En plaçant la barre à 10^6, j'élimine le Python ![tongue](img/smilies/tongue.png)
@emmaenne : le problème initial est le suivant : "Un prisonnier tiré au hasard parmi 100 est amené chaque jour dans une pièce où se trouve une ampoule, allumée ou éteinte, dans l'état dans lequel l'a laissée le prisonnier précédent. Les prisonniers seront libérés si l'un d'eux affirme un jour, avec raison, que tout le monde est déjà passé dans la pièce. Les prisonniers ne communiquent pas entre eux, sauf au tout début, pour mettre au point une stratégie gagnante".
La solution à ce problème est : "Le premier prisonnier amené dans la pièce allumera l'ampoule chaque fois qu'elle est éteinte. Les autres l'éteindront la première fois qu'ils la verront allumée, puis n'y toucheront plus. Lorsque le premier prisonnier aura allumé la lumière 100 fois, il pourra affirmer à coup sur que tout le monde est passé.".
Ca marche, puisque les 99 prisonniers vont, à terme, éteindre la lumière, tous chacun une et une seule fois. Si le premier l'allume 100 fois, cela signifie donc que les 99 autres sont passés l'éteindre (puisque chacun ne l'éteint qu'une fois).
Par contre, si cette méthode marche, elle peut s'avérer longue, les prisonniers étant amenés aléatoirement. Du coup, le problème ici était de trouver la durée moyenne de jeu, en fonction du nombre de prisonniers.
Pour deux prisonniers par exemple : le jeu s'arrête quand 1 est passé, puis 2, puis 1 repassé. Chaque prisonnier passe avec une probabilité de 1/2, sauf le 1er jour (qui détermine en fait qui sera le premier prisonnier). Par exemple: > 1 - 2 - 1 (3 jours) arrivera avec une probabilité de 1/4 > 1 - 2 - 2 - 1 (4 jours) arrivera avec une probabilité de 1/8 > 1 - 1 - 2 - 1 (4 jours aussi) arrivera avec une probabilité de 1/8 aussi > 1 - 1 - 1 - 2 - 1 (5 jours) arrivera avec une probabilité de 1/16 > 1 - 1 - 2 - 2 - 1 (5 jours) arrivera avec une probabilité de 1/16 > 1 - 2 - 2 - 2 - 1 (5 jours) arrivera avec une probabilité de 1/16 > 1 - 1 - 1 - 1 - 2 - 1 (6 jours) arrivera avec une probabilité de 1/32 > 1 - 1 - 1 - 2 - 2 - 1 (6 jours) arrivera avec une probabilité de 1/32 > 1 - 1 - 2 - 2 - 2 - 1 (6 jours) arrivera avec une probabilité de 1/32 > 1 - 2 - 2 - 2 - 2 - 1 (6 jours) arrivera avec une probabilité de 1/32 etc...
Plus globalement, - 1 passe, puis repasse un certain nombre de fois - 2 passe, puis repasse un certain nombre de fois - et enfin 1 repasse.
Or, et c'est le résultat préliminaire, si un événement se produit avec une probabilité p, alors le nombre de fois consécutives où il se produira est, en moyenne, de p/(1-p). Exemples - tu lances le dé en comptant le nombre de fois où le 6 ne sort pas (5/6) : en moyenne il y aura 5 lancers consécutifs. - pareil, pour sortir pile sur une pièce (1/2), en moyenne tu auras 1 lancer.
Donc, là, en moyenne toujours - 1 passe - puis repasse un certain nombre de fois ==> en moyenne 1 fois - 2 passe - puis repasse un certain nombre de fois ==> en moyenne 1 fois - et enfin 1 repasse. Soit 5 fois au total.
Pour trois prisonniers, pareil : - 1 passe - puis repasse un certain nombre de fois ==> en moyenne 1/2 fois - 2 passe - puis 2 ou 3 repassent un certain nombre de fois ==> en moyenne 2 fois - 1 repasse. - puis 1 ou 2 repassent un certain nombre de fois ==> en moyenne 2 fois - 3 passe - puis 2 ou 3 repassent un certain nombre de fois ==> en moyenne 2 fois - et enfin 1 repasse. Total : 11.5 passages en moyenne.
Et enfin, pour un nombre de prisonniers N, on trouve le résultat ci-dessus.
#8 - 04-08-2015 11:31:16
- scrablor
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 964
Prisonniers, ampoules, et durée de eu + Indices
OK pour la stratégie, mais les probabilités réelles sont inférieures. Pour deux prisonniers, quand n°2 passe, il sait qu'il est le dernier. Donc la moyenne est de 3 jours. Pour trois prisonniers, imaginons la séquence : n°1-n°2-n°1-n°3-n°2. Comme n°2 voit que la lampe est éteinte, il sait que ce n'est pas n°1 qui l'a précédé. Il dira donc avant n°1 que tout le monde est passé... Pour davantage de prisonniers, il y aura aussi des situations où n°1 ne sera pas le premier informé. Le calcul me semble impossible ![sad](img/smilies/sad.png)
Celui qui fuit les casse-tête ne vaut pas un clou.
#9 - 04-08-2015 12:17:35
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1958
Prisonniers, ampoules, et duurée de jeu + Indices
Bien vu! En effet, pour n =2, on peut trouver moins. Pour n=3 aussi. Plus rapide même, 1-2-3-2. 2 sait que 1 est passé, puisque la lumière est allumée la 1ère fois, et il sait que 3 est passé la 2nde fois : ça n'est pas lui, ni 1 puisque la lumière est toujours éteinte. Pour n=4, on pourrait aussi imaginer 1 - 2 - 1 - 3 - 2 - 1 - 2 - 4 - 2 Le 2 sait que le 1 est passé au début, il sait aussi que quelqu'un est passé la 2nde fois, et devine que le 4 est passé à la fin en voyant la lumière allumée puis éteinte.
Le problème, c'est qu'il y a des cas où 2 ne saura jamais si tout le monde est passé ou pas. Genre 1 - 2 - 1 - 3 - 1 - 4 - 2 : il sait qu'au moins 2 sont passés, pas plus. Donc la stratégie ne couvre pas tous les cas. Les prisonniers doivent mettre au début au point une stratégie qui couvre tous les cas possible.
Ceci dit, la valeur moyenne change, mais pas des masses : déjà, il faut que tout le monde soit passé allumer ou éteindre la lumière. Donc ça joue sur la fin, le terme "(2-N)* 1".
Ca pourrait être un problème sympa : quelle est la plus courte séquence possible permettant à un prisonnier d'affirmer que tout le monde est passé ?
Allez, je lance un autre topic !
Mots clés des moteurs de recherche
|
![](/img/vague-haut-droite.png) |