Enigme Prisonniers, ampoules, et durée de jeu + Indices @ Prise2Tete

scarta · #1

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]

Indice 2 : premiers résultats
Spoiler : [Afficher le message]

scarta · #2

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

Franky1103 · #3

Bon, ben le flop...

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.

emmaenne · #4

En fait, je ne comprends pas ces problèmes, ni ce que l'on cherche, ni la solution donnée. Désolé.

Promath- · #5

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

Vasimolo · #6

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

La prochaine énigme sera la bonne

Vasimolo

scarta · #7

@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
En plaçant la barre à 10^6, j'élimine le Python

@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.

scrablor · #8

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

scarta · #9

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 !

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

#1 - 29-07-2015 10:47:27

Prisonniers,, ampoules, et durée de jeu + Indices

#0 Pub

#2 - 03-08-2015 12:07:58

Prisonniers, ampouels, et durée de jeu + Indices

#3 - 03-08-2015 15:07:53

Prisonniers, ampoules, et durrée de jeu + Indices

#4 - 03-08-2015 17:00:26

Prisonniers, ampoles, et durée de jeu + Indices

#5 - 03-08-2015 18:52:02

Prisonniers, ampoules, et durée de jeu + Idices

#6 - 03-08-2015 18:52:09

Prisonniers, ampoules, et dure de jeu + Indices

scarta a écrit:

#7 - 03-08-2015 18:53:17

prisonniers, ampoules, et durée de jeu + infices

#8 - 04-08-2015 11:31:16

prisonniers, ampiules, et durée de jeu + indices

#9 - 04-08-2015 12:17:35

prisonniers, ampoules, et durée de keu + indices

Réponse rapide

Sujets similaires

Mots clés des moteurs de recherche

Pied de page des forums