Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

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

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1430

prisonniers, ampoules, er durée de jeu + 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



Annonces sponsorisées :

 
Réponse :
  • |
  • Répondre

#0 Pub

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

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1430

Prisnoniers, ampoules, 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 : 2706
Lieu: Luxembourg

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

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.

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

emmaenne
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 3057
Lieu: Au sud du Nord

Prisonniers, ampoules, et durée d 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 dureé 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 : 4733

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

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

La prochaine énigme sera la bonne smile

Vasimolo

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

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1430

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

@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 : 931

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

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


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 : 1430

prisonniers, ampoules, et dyré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 !

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez (numériquement) à la petite énigme suivante : 

Si il y a 51 pommes et que vous en prenez 24, combien en avez-vous ?

Sujets similaires

Mots clés des moteurs de recherche

Mot clé (occurences)

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete