Écrire une réponse @ Prise2Tete

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	[+]

	Forum » Enigmes Mathématiques » Prisonniers, ampoules, et durée de jeu + Indices Écrire une réponse Attention : Aucun indice ou demande d'aide concernant les énigmes de Prise2Tete n'est accepté sur le forum ! Rends-toi sur le cercle des sages si tu as besoin d'aide ! Tout nouveau message ou sujet ne respectant pas cette règle sera supprimé, merci. Rédige ton message Nom Courriel \| \| \| \| Upload \| Aide Message [quote=scarta]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 (zp^z (1-p), z>=0) = (1-p)somme (zp^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[/quote] Options Ne pas convertir les émoticônes sur ce message Sécurité Répondez à la devinette suivante : Le père de toto a trois fils : Riri, Fifi et ?* Retour Résumé de la discussion scarta 29-07-2015 10:47:27 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] 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