Devinette, 100 Prisonniers

[invite35452583]

Ce qui me pose problème, c'est le passage de cette durée moyenne à un simple ajout sur le temps qu'aurait mis en moyenne le compteur pour faire ses 99 visites... je ne comprend pas ce qui permet de faire ce raccourci. C'est une approximation ou une valeur exacte ?

C'est une approximation, je pense. Plus exactement, pour moi c'en est une maintenant parfois des raccourcis se révèlent exacts même si ce n'est pas évident au départ.
Si l'approximation était exacte on aurait :
1 jour (désignation du 1er prisonnier qui devient compteur)
100/99 jour pour qu'un nouveau prisonnier entre dans le salon
100 jours pour que le compteur repasse par le salon
100/98 jour pour qu'un nouveau prisonnier entre dans le salon
...
Ce n'est donc qu'une approximation car le calcul exact demanderait un arbre complet qui ne supporterait pas très bien des 1,1..jour.
La valeur obtenue serait 10519 jours à 1 jour près. C'est une approximation meilleure que 10000 mais qui reste grossière en tout cas plus grossière que je ne pensais.
-----

[invite970ffd48]

es-ce possible de calculé la probabilité à partir d'une sorte de système d'addition de % de chance,(les stat ce n'est vraiment pas mon domaine) je m'explique donc étape 1 100% chance d'établir le conteur, étape 2 99 % chance qu'un nouveau passe étape 3 1% de chance que le compteur passe à nouveau étape 4 98 % chance pour un nouveau étape 5 1 % chance que le compteur passe, étape 6 97 % de chance etc etc. ... jusqu'à 1 % et 1% puis la fin ..... je sais que se que je dis a un minimum de logique mais je n'ai aucune idée comment calculé cela, es-ce un peu la même chose que votre approche ?

[Médiat]

C'est une approximation, je pense.

Pour moi c'est une probabilité, ou plutôt une espérance.

Je reprends le calcul de cadors :

1 jour le compteur est déterminé (cela fait 1 jour de passé)

ensuite il faut qu'un prisonnier différent ce celui-ci soit choisi, et cela peut avoir lieu :
le jour 1 avec une probabilité de 99/100
le jour 2 avec une probabilité de (1/100 (pour avoir le compteur le jour 1) x 99/100 (pour avoir un autre prisonnier le jour 2) c'est à dire 99/10000.
...
le jour n avec une probabilité de (1/100)^(n-1) (pour avoir le compteur pendant n-1 jours) x 99/100 ) c'est à dire 99/100^n

L'espérance de cette variable aléatoire est 1 x 99/100 + 2 x 99/10000 + ... 99/100^n + ... = 1.01.

Puis le compteur, puis un autre choisi parmi 98, puis le compteur ....

Bien sur cette méthode est exactement celle développée par homotopie, et pour moi, ce n'est pas une approximation, mais une espérance exacte (si homotopie n'avait pas trouvé le même résultat numérique que moi j'aurais pu soupçonner avoir fait une erreur de calcul, mais là j'ai confiance).

A tout hasard la somme de la série harmonique est ln(99) + 0.5772 + 1/198 (avec une précision de l'ordre de 1/1988)

[yat]

Si l'approximation était exacte on aurait :
1 jour (désignation du 1er prisonnier qui devient compteur)
100/99 jour pour qu'un nouveau prisonnier entre dans le salon
100 jours pour que le compteur repasse par le salon
100/98 jour pour qu'un nouveau prisonnier entre dans le salon

Voilà ou était mon incompréhension : je raisonnais à l'envers. Pour moi il fallait calculer le temps moyen entre deux passages du compteur, et ensuite en fonction du nombre de prisonniers restants, la probabilité que la lampe soit éteinte quand il passe.

En fait, c'est vrai qu'il est beaucoup plus futé de commencer par attendre qu'un prisonnier passe éteindre la lumière, et ensuite attendre le prochain passage du compteur. Ca devient beaucoup plus facile à calculer, et j'obtiens exactement la même chose que vous.

Et je rejoins Mediat sur la deuxième question : il s'agit bien de la valeur exacte de la moyenne, ou de l'espérance. En effet, le fait de ne pas obtenir des nombres de jours entiers n'est pas un problème, puisqu'il s'agit d'une moyenne.

Par contre, je ne m'explique pas l'écart de 10 jours que j'obtiens avec une effroyable constance quand je fais mes simulations...

Et en ce qui concerne les méthodes pour réduire cette moyenne, personne n'a de piste ?

[Médiat]

Par contre, je ne m'explique pas l'écart de 10 jours que j'obtiens avec une effroyable constance quand je fais mes simulations...

Je tenterai une simulation ce soir et te tiendrai au courant (sauf si homotopie le fait avant moi (n'hésite surtout pas, homotopie )

Et en ce qui concerne les méthodes pour réduire cette moyenne, personne n'a de piste ?

Appeler les prisonniers toutes les minutes plutôt que tous les jours (plus vite ne serrait pas raisonnable)

Il y a deux erreurs dans mon post #63 :
L'espérance de cette variable aléatoire est 1 x 99/100 + 2 x 99/10000 + ... n*99/100^n + ... = 1.01.
et
avec une précision de l'ordre de 1/198

[invite28ccf7ab]

La réponse est d'une simplicité ....

le premier prisonnier, sorti pour la première fois de sa cellule, dit la phrase et il est 100% sûr d'avoir raison, puisque la veille les 100 prisonniers étaient réunis dans le salon.

c'est pas ça??

[invite970ffd48]

Et si les prisonniers avaient été réunis dans la cour ?

[Médiat]

Je tenterai une simulation ce soir et te tiendrai au courant (sauf si homotopie le fait avant moi (n'hésite surtout pas, homotopie )

Il va falloir que homotopie s'y colle, car je n'avais pas fait attention, tu as fait 10 x 400 000 test de 10 000 tirages (au moins), c'est à dire 40 000 000 000 de tirages, avec ma petite machine il me faudrait 70 jours

[invite970ffd48]

vous faites vos test avec quel machine/programme/ magie ???

[yat]

vous faites vos test avec quel machine/programme/ magie ???

Juste un pitit programme en C. La stratégie des prisonniers est très simple à coder.

[invite35452583]

Bien sur cette méthode est exactement celle développée par homotopie, et pour moi, ce n'est pas une approximation, mais une espérance exacte (si homotopie n'avait pas trouvé le même résultat numérique que moi j'aurais pu soupçonner avoir fait une erreur de calcul, mais là j'ai confiance).

C'est la valeur trouvée par simulation par yat qui m'a poussé à être modeste (vu l'écart entre valeur théorique et valeur issue des simulations, surtout de cet ordre, je soupçonnais une complication).
On peut aussi le voir ainsi :
notons t1 le temps moyen :
on a deux cas possibles :
1) le compteur est rappelé proba 1/100, temps moyen dans ce cas t1+1 (on est revenu à la situationinitiale décalé d'un jour)
2) un autre prisonnier est rappelé proba 99/100, temps moyen t2
On a t1=(1/100)(t1+1)+(99/100)t2
(99/100)t1=(99/100)t2+1/100
t1=t2+1/99 (1/99=100/99-1)
On a ensuite t2=t3+99 avec la même méthode où t3 est le temps moyen dans le cas où tout va bien jusqu'au 3ème jour compteur-1 autre prisonnier juste après puis tout de suite le compteur.
t3=t4+2/98 (2/98=100/98-1)
...
t(100+99)=t198+99
Or t199=199 (si tout se passe bien pendant ces 199 jours, le procesus s'arrête ce jour là)
D'où t1=199+1/99+99+2/98+99+...+98/2+99+99/1+99=1+99x(1+99)+(1+1/99)+(1+2/98)+...+(1+98/2)+(1+99/1)=1+99x100+100(1/99+1/98+...+1/2+1)=10420,.. jours.
Finalement l'écart est faible (l'essentiel de l'écart que j'avais vu moi, environ 110, est que je n'avais pas fait attention vient du fait que l'on attend le compteur 99 fois et non 100 ). yat pourrais-tu dire ce que tu as demandé de faire à ton programme quand le jeu n'aboutissait pas en temps fini ? L'écart relatif est très faible et le fait que tu obtiennes toujours à peu près la même valeur est "naturelle" : la moyenne est stable pour la simulation mais qui n'est qu'une simulation qui calcule le temps moyen d'une expérience aléatoire qui diffère un peu de la situation "réelle" du jeu en question. yat pourrais-tu reprendre en modifiant le temps maximal que tu accordes aux prisonniers pour être libérés et regarder l'évolution en fonction de ce max ?

[yat]

yat pourrais-tu dire ce que tu as demandé de faire à ton programme quand le jeu n'aboutissait pas en temps fini ?

De continuer

C'est le cas limite de ce qui peut se produire dans la théorie. La probabilité qu'au bout de n jours le jeu ne soit pas terminé tend vers zéro quand n tend vers l'infini. Donc dans la pratique, ça ne risque pas d'arriver. En tout cas, sur mes 4 millions d'essais, ça ne s'est jamais produit, sinon ils tourneraient encore, parce que je n'ai absolument pas géré ce genre de chose.

L'écart relatif est très faible et le fait que tu obtiennes toujours à peu près la même valeur est "naturelle" : la moyenne est stable pour la simulation mais qui n'est qu'une simulation qui calcule le temps moyen d'une expérience aléatoire qui diffère un peu de la situation "réelle" du jeu en question. yat pourrais-tu reprendre en modifiant le temps maximal que tu accordes aux prisonniers pour être libérés et regarder l'évolution en fonction de ce max ?

Ben justement, comme il n'y a pas de max, je ne vois pas ce qui diffère entre ma simulation et la situation réelle (enfin, mis à part le fait qu'en réalité le choix des prisonniers n'est pas aléatoire).

[invite74a6deb6]

les ampoules on une duree de vie limiter et connu, on peut se servir de ca?

[invite35452583]

Ben justement, comme il n'y a pas de max, je ne vois pas ce qui diffère entre ma simulation et la situation réelle (enfin, mis à part le fait qu'en réalité le choix des prisonniers n'est pas aléatoire).

Moi non plus je ne vois pas. Certes, l'alea n'est qu'une imitation mais un écart relatif d'environ d'1/1000 ça fait grosse erreur pour les bécanes actuelles.

Enfin par rapport au problème initial, le principal est que dans les deux (théoriques et simulés) l'essentiel du temps est consommé en attente du compteur. Réduire de manière importante ce temps me paraît pour l'instant surréaliste car je ne vois vraiment pas comment se passer d'un compteur unique.

[invite970ffd48]

le seul moyen que je vois serais d'intégré un deuxiemme compteur mais pour ce faire il faudrait qu'un troisième paramètre permette au compteurs de communiqué, exemple, le premier compteur qui arrive à 50 laisse l'interrupteur dans un état entre éteint et ouvert ainsi lorsque le second compteur passe il peut immédiatement ajouté 50 à son compte et ainsi on devrait théoriquement coupé le temps en deux ... mais es-ce légal de placé l'interrupteur a mi-chemin entre ouvert et fermé ??

[invite970ffd48]

révision de mon dernier post avec un troisièmme paramètre il serait possible de mettre un nombre X de compteurs a condition que le nombre à atteindre pour chaque compteur soit inversement proportionnel au nombre de compteur, exemple 10 compteurs, chacun place l'interupteur à mi-chemin lorsqu'il atteint 9 ( 10 avec lui même ) ... heu je me rend compte que dans un tel cas il faudrait un compteur en chef qui pourrais calculé le nombre de compteur ayant atteint et celui-ci devrait arrêté de compté les prisonnier après 9 pour que chaque compteur puisse avoir 9 prisonnier à compté afin de fournir l'information au compteur en chef ... !!!

aussi avec un gradateur il pourrait y avoir plusieurs état intermédiaire donc cela faciliterais le comptage !



quelqu'un comprend ce que je viens d'écrire ? si oui essayé de mathématiser le tout ! bonne chance !

[yat]

Je crois que j'ai une piste pour intégrer un compteur supplémentaire, voire même donner potentiellement à chaque prisonnier le rôle de compteur, en fonction de ce qui se passe.

Le problème c'est que ça me semble un peu plus compliqué à calculer, surtout que ça fait intervenir pas mal de paramètres, qu'il faudrait optimiser.

Grossièrement, un exemple avec un compteur principal et un compteur auxiliaire :
Le compteur principal et les prisonniers "normaux" gardent le même mode opératoire que pour la solution précédente (le compteur allume la lumière, les prisonniers l'éteignent). Le compteur auxiliaire démarre le jeu avec son compteur interne à 1 (il s'est compté lui même). Quand il entre dans la pièce, s'il voit l'ampoule allumée, il l'éteint et décrémente son compteur (sans passer en dessous de zéro), et s'il voit l'ampoule éteinte il l'allume et incrémente son compteur.
En début de partie, le compteur auxiliaire permet d'accélérer le décompte, puisque l'attente d'un compteur passe de 100 à 50 jours (mais ça n'accélère pas le rythme d'incrémentation du compteur principal). Quand les nouveaux prisonnier se font rares, le compteur auxiliaire accélère cette fois le rythme des extinctions d'ampoules (et donc l'incrémentation du compteur principal), puisqu'il joue à chaque tour le rôle d'un nouveau prisonnier supplémentaire. Par contre, ceci occasionnera un ralentissement dans l'hypothèse ou le compteur auxiliaire aura atteint une valeur trop élevée, ce qui forcera à attendre pendant une longue série de périodes de 100 jours pour que l'auxiliaire déverse son compteur dans le principal. Je ne sais pas si cela pourrait vraiment être handicapant, pusique normalement à mesure que le jeu se déroule, il devrait de plus en plus souvent trouver une ampoule éteinte et se décrémenter, mais si c'est le cas il suffit peut-être de limiter la valeur maximale de son compteur à une valeur arbitraire...

Un deuxième exemple ou tous les joueurs sont compteurs auxiliaires (sauf le compteur principal)... Tous ont leur compteur à 1, ceux qui trouvent une ampoule allumée passent à zéro en l'éteignant, et restent en mode passif : ils n'interviendront plus sur l'ampoule. Les autres font évoluer leur compteur comme précédemment, et le limitent d'une manière ou d'une autre, pour éviter qu'ne fin de partie on se retrouve avec 30 compteurs qui ne cessent de s'échanger leurs points en coupant l'herbe sous les pieds du compteur principal qui ne pourra pas faire augmenter le sien.

Pour ce genre de solution, j'ai un peu de mal à evaluer le temps moyen... Je ferais bien une simulation, mais comme la dernière est fausse, il faut d'abord que je corrige le problème pour espérer avoir quelque chose d'un peu plus fiable.

Entre temps, si quelqu'un veut suivre ces pistes...

P.S : cadors, étendre le problème à un interrupteur à trois positions est intéressant, parce que ça doit permettre d'élaborer une stratégie beaucoup plus complexe, mais je ne pense pas qu'on ait atteint l'optimal du problème initial.

[Quintilio]

C'est interessant comme approche. C'est vrai que ca doit pouvoir permettre de diminuer la duree du jeu.
Pour optimiser encore un peu, on peut considerer que tous les prisoniers ne deviennent compteur auxiliaires que s'ils se sont deja decomptes. Cad qu'ils ne peuvent incrementer leur compteur seulement une premiere decrementation.
Ca permet d'augmenter progressivement au cours du temps le nombre de compteurs auxiliaires. Parce qu'il me semble preferable d'en avoir peu au debut (parce que sinon le compteur a un chance sur deux de passer apres un compteur auxiliaire qui aurait allume la lumiere ce aui augmenterais le nombre de tours a vide du compteur) et plus a la fin (pour encore diminuer le nombre de tours a vide, le compteur a toujours une chance sur deux de trouver la lumiere eteinte mais la la proba est superieure a celle sans compteurs auxiliaires)
En fait la solutin de yat permet tout de meme d'optimiser le temps de comptage, mais dans tous les cas il faudra toujours au moins 99 passage au compteur principal pour compter les 99 autres prisoniers ce qui fait toujours 27 ans. Dans le message #1 il est dit que la moyenne peut etre ramenee a 10 ans, seulement la je vois pas comment. Soit le compteur doit passer tous les 30 jours, soit il faut 3 compteurs et dans ce cas il faut pouvoir les synchroniser pour que le dernier puisse savoir quand les autres on finis

[invite970ffd48]

je ne suis pas sur que de transféré des valeurs à d'autres compteurs auxiliaires en incrémentant leur valeur permette de faire augmenté le rythme de calcul du comtpeur principal, en bout de ligne il lui faudra 99 passage ...

ceci pourrais accélé le temps de "demi-vie" du jeu si je peux m'exprimé ainsi, en ce sens qu'il faudrait beaucoup moins de temps pour que la moitié des prisonniers soit passés et compté par un des 2 compteur, mais autant pour que le compte total soit fait...

le suel moyen que je vois d'accélé le temps du calcul est vraiment de trouvé un moyen de calculé plus d'un prisonniers en un seul passage ... et pour cela je crois qu'il faut introduire un troisième paramètre ...

[Quintilio]

C'est clair que comme les prisonniers sont comptes un par un il faudra de toute maniere au moins 99 passages pour tous les compter. Mais le systeme des compteurs auxilieres permet d'eviter les tours "a vide" du compteur principal lorsqu'il reste peu de prisoniers a compter. Cad que la probabilite que le compteur principal trouve le lumiere allume diminue (lorsqu'il reste peu de prisoniers a compter), parce que les compteurs auxiliaires eux aussi peuvent eteindre la lumiere.
Mais bien evidemment comme je l'avais dit plus haut la duree moyenne de temps de jeu ne peut pas etre inferieur a 99x100 jours. Si on veut vraiment pouvoir diminuer la moyenne il faut plus de compteurs mais ils auront besoin d'indiquer aux autres compteurs quand ils ont finis de compter (ils devissent l'ampoule, on considere que l'interrupteur a 3 positions...) Meme si la on s'ecarte un peu de l'ennonce original, ca peu etre interessant de savoir quel est le nombre de compteur qui permetterait d'optimiser le temps de comptage.

[invite970ffd48]

effectivementsa pourrais être intéressant de voirl'optimistion, par contre pour se qui est de la diminution des tour a vide je crois plutôt que se sytèmme augmenterais le nombre de "tours à vide du compteur principal"

le fait est qu'au début le compteur auxillière verrais sa valeur augmenté puisqu'il y aura plus de chance pour lui de trouvé un ampoule éteinte qu'allumé , et vers la fin lorsqu'il aura compté 10 ou 15 prisonniersil devra repassé 10-15 fois sur une ampoule allumé pour "transféré" son compteau compteur principal cependant à ce moment on tombe à 1/100(compteur Principal ) + 1/100 (compteur auxi.)+ 1/100 (compteur P compteur princpal) ....1/100 (comptuer auxi )+ 1/100 ( compteur principal ) FIN

alors qu'avec un seul compteur les dernière étapes se produise plus rapidement

1/100 (compteur) + 2/100 (prisonnier) 1/100 (compteur) 1/100 (prisonnier) 1/100 (compteur) FIN

Selon moi lA,ajout d,Un compteur auxiliaire allongerait le temps car le compteur principale risquerais d'avoir plus de " tours à vide "

[Médiat]

Concrètement, sur 10 jeux de 400 000 tests, j'obtiens une fois une moyenne de 10407 jours, et 9 fois une moyenne de 10406 jours. Est-ce que ça ressemble à ce que vous obtenez ?

J'ai refais ma simulation (en C cette fois), après 10 jeux de 400 000 tests (évidemment ), j'obtiens des résultats entre 10230 et 10487, ce qui ne confirme pas la moyenne à 10 près bien sur, mais montre (et je n'en suis pas surpris) que l'écart type n'est pas négligeable. Du coup, je trouve très étrange que tes résultats soient quasiment identiques pour tes 10 jeux (peut-être un problème d'initialisation du générateur aléatoire ?).

[yat]

J'ai refais ma simulation (en C cette fois), après 10 jeux de 400 000 tests (évidemment ), j'obtiens des résultats entre 10230 et 10487, ce qui ne confirme pas la moyenne à 10 près bien sur, mais montre (et je n'en suis pas surpris) que l'écart type n'est pas négligeable. Du coup, je trouve très étrange que tes résultats soient quasiment identiques pour tes 10 jeux (peut-être un problème d'initialisation du générateur aléatoire ?).

Sur 400 000 tests, même avec un écart type non négligeable, moi je suis quand même surpris que tu puisses obtenir entre deux jeux un écart de plus de 2%...

En ce qui concerne le générateur aléatoire, les 10 jeux de tests sont enchainés dans le programme, je ne relance pas 10 fois à la main. Donc je ne réinitialise pas le générateur avant chaque jeu.

Je joins le code de mon programme, au cas où quelques bananes te sauteraient aux yeux.
Peux-tu aussi joindre le tien ? Histoire de comparer les méthodes...

EDIT : il faut noter qu'il y a un écart de 1 entre les résultats que j'avais obtenu la première fois et ceux que j'obtiens maintenant : avant j'initialisais le nombre d'étapes à 0 au départ au lieu de commencer à 1.

[Médiat]

Peux-tu aussi joindre le tien ? Histoire de comparer les méthodes...

Oui je le posterai ce soir (j'espère pas trop tard , merci les embouteillages du vendredi soir ).

[invite73fcb399]

Les prisonniers se rencontrent pour établir un plan..et quoi de plus accueillant qu'un salon pour détérminer leur plan??

Ainsi il sont tous passés dans le salon et il peuvent faire leur affiramtion et avoir juste.

[Médiat]

Sur 400 000 tests, même avec un écart type non négligeable, moi je suis quand même surpris que tu puisses obtenir entre deux jeux un écart de plus de 2%...

Rien que pour le passage du compteur, la moyenne est 100 jours, mais l'écart type est quasiment de 100 jours (99,5), même si cela doit se compenser sur 400 000 tirages, je ne suis pas choqué d'un écart de 2% (ne pas être choqué ne démontre rien, bien sur)

[invité576543]

Rien que pour le passage du compteur, la moyenne est 100 jours, mais l'écart type est quasiment de 100 jours (99,5), même si cela doit se compenser sur 400 000 tirages, je ne suis pas choqué d'un écart de 2% (ne pas être choqué ne démontre rien, bien sur)

Environ 100 pour un passage. Mais pour 100 passages, on tombe déjà à 1000, soit 10%. Sur 400000 tirages (en imaginant qu'un tirage = une partie), en appliquant en première approximation la racine carrée, ça tombe à moins de 0.02%, non?

Cordialement,

[inviteea6fd0dc]

Franchement, cela fait cinq pages que pas mal de membres cherchent la solution, et pas des moindres (je ne cite personne pour ne pas faire de jaloux).

Alors .... vous voudriez que les prisonniers aient trouvé

C'est gardien qui a gagné

PS Pour la quinzaine qui participe, cela fait déjà pas mal de difficulté pour se mettre d'accord, alors pour cent prisonniers (chacun pour soi de plus).

Si, peut être bien que le gardien est mort de vieillesse en attendant la détention.... ou d'un infar en voyant le b....l que cela déclenchait

[invité576543]

J'ai refais ma simulation (en C cette fois), après 10 jeux de 400 000 tests (évidemment ), j'obtiens des résultats entre 10230 et 10487, ce qui ne confirme pas la moyenne à 10 près bien sur, mais montre (et je n'en suis pas surpris) que l'écart type n'est pas négligeable. Du coup, je trouve très étrange que tes résultats soient quasiment identiques pour tes 10 jeux (peut-être un problème d'initialisation du générateur aléatoire ?).

Les valeurs 10230 et 10487 sont les valeurs min et max des 4 000 000 de valeurs obtenues? Ou les valeurs min et max des 10 moyennes?

Si c'est le premier cas, ça explique le 2%, il me semble...

Cordialement,

[Médiat]

Salut mmy,

Les valeurs 10230 et 10487 sont les valeurs min et max des 4 000 000 de valeurs obtenues? Ou les valeurs min et max des 10 moyennes?

Si c'est le premier cas, ça explique le 2%, il me semble...

Non c'est le min et le max des 10 moyennes de 400 000 tests (malheureusement).

Je vérifie mon code ce soir et je reviendrai

Cordialement,