Aller au contenu
  • 0
akasolace

Le gourou et ses adeptes

Énigmes

Ceci est un énigme du site défi turing sur laquelle je bloque depuis très longtemps.

 

J'ai essayé plusieur approches sans succès. Je serais ravi d'avoir des opinions sur comment résoudre ce problème.

J'ai essayé la technique ou un prisonier compte. Pour des questions de symétrie et étand donné que l on sait que la lampe est éteinte au début, je pensais que l'optimal serait de définir comme compteur le premier qui rentre 2 fois dans la pièce. Soit j'ai fais une erreur dans mon code ou alors il y a une approche encore plus optimale ....

 

 

"Un gourou a enfermé ses 33 adeptes chacun dans une pièce de son immense manoir. Les adeptes ne peuvent pas communiquer entre eux.
Le gourou habite dans une chambre luxueuse de son manoir, dans laquelle se trouve la "lampe de la vérité". Il propose un jeu initiatique à ses adeptes. Chaque jour, il emmènera dans sa chambre un adepte tiré au sort en secret. Là, ce dernier sera libre d'actionner ou non l'interrupteur de la lampe. Le gourou ne touchera jamais la lampe, qui est éteinte au début du jeu.
L'enjeu est le suivant : si un adepte, quand il pénètre dans la chambre du gourou, affirme que tous les adeptes sont déjà venus au moins une fois dans cette chambre et qu'il a raison, les 33 adeptes seront libérés. En revanche, s'il a tort, tous les adeptes entameront un transit vers Vénus...
Avant que le jeu commence et que les adeptes soient isolés dans leur chambre, ils ont un moment pour mettre au point une stratégie. Leur seul moyen de communiquer sera la "lampe de la vérité".

Le fichier tirage.txt contient le résultat de 10'000 tirages au sort du gourou (des numéros de 1 à 33, indiquant la chambre de l'adepte). Sur la ligne 1 se trouve le numéro de l'adepte appelé le premier jour, sur la ligne 2 l'adepte du deuxième jour, etc. Ce fichier ne peut évidemment pas être utilisé pour définir une stratégie, puisque les adeptes n'y ont pas accès.

S'ils découvrent la bonne stratégie, après combien de jours les adeptes seront-ils libérés ?"

 

Partager ce message


Lien à poster
Partager sur d’autres sites

13 réponses à cette énigme

Messages recommandés

  • 0
Révélation

On peut donner la consigne : la lumière doit être éteinte, sauf si c'est la première fois qu'un adepte est dans la chambre du gourou, auquel cas elle sera allumée.

Chaque adepte regarde chaque jour si la lumière est allumée et mémorise le nombre de jour où la lampe a été allumée.

Si un adepte qui a vu 32 fois la lampe annulée arrive dans la chambre du gourou, alors qu'il n'y est jamais allé, il affirme que tous les adeptes sont déjà venus au moins une fois dans cette chambre, et il a raison, et il n'était pas possible d'être plus rapide pour le dire, puisque auparavant un adepte (lui) n'était pas venu.

si j'ai bien compris l'énoncé. Mais le nombre de jour dépend de la suite choisie par le gourou...

Partager ce message


Lien à poster
Partager sur d’autres sites
  • 0

 

Quote

si j'ai bien compris l'énoncé. Mais le nombre de jour dépend de la suite choisie par le gourou...

 

effectivement dans l'énoncé du problème il y a un fichier texte qui donne l'order dans lequel le gourou les appelle. 

 

@ribi  J'étais effectivement partis sur cette approche. La lumière étant éteinte, le premier qui rentre 2 fois dans la piece et vois la lumiere éteinte l'allume a partir de ce moment ce sera le seul ayant le droit d'allumer la lampe. Aussi a partir de la, celui qui compte sait que au moins 2 prisonniers sont rentrés dans la pièce (lui et celui qui a allummé).  Il doit donc compté encore 31 passages. Les prochains prisonniers qui rentrent dans la pièce peuvent éteindre la lampe si elle éteinte et qu'ils ne l'ont encore jamais éteinte.

Le compteur saura ainsi quand les 33 sont passés.

Malheureusement cela ne donne pas la réponse attendue (je ne pense vraiment pas avoir fais une erreur d'implémentation...)

 

 

Partager ce message


Lien à poster
Partager sur d’autres sites
  • 0

Est-ce que tout le monde peut compter ?

Est-ce que tout le monde voit la lampe de la vérité ?

Je ne comprends pas pourquoi tu comptes ceux qui rentrent deux fois dans la pièce ?

Partager ce message


Lien à poster
Partager sur d’autres sites
  • 0

En fait, il y a 3 étapes

 

Etape 1: du jour 1 au jour n-1 (n étant le nb de prisonniers)

Le premier qui rentre 2 fois dans la pièce allume la lampe

Celui qui allume la lampe devient le compteur, il allume la lampe le jour k.

Aors il sait que los des k premiers jours il y a eu k-1 (incluant lui) prisonniers différents qui sont rentrés dans la pièce. Il lui reste donc a compter 

 

 

Etape 2: le jour n n

Si au jour n la lampe est toujours éteinte alors victoire, sinon le prison  éteint la lampe.

 

 

Etape 2: a partir du jour n+1

 - Un prisonier qui a vu la lampe éteinte durant l'étape 1 ne fais rien (car il fait partit des k-1 prisonniers qui ont déja été comptabilisé-

 - Les autres prisonniers qui rentrent dans la pièce:  si la lampe est éteinte ET  n'ont pas encore allumé la lampe durant la phase 2  => allume la lampe

 - Le compteur s'il rentre dans la pièce et la lampe est allumé, il l'éteint et incrémente de 1son compteur

 

Quand son compteur arrive à n,  il déclare que les n prisonniers sont rentrés dans la pièce.

 

Je trouvais que c'était le meilleur algorithme pour ce problème mais ma solution est refusée (je trouve le jour 703 avec les données d'entrée donc a priori on peut faire mieux)....

 

     

Partager ce message


Lien à poster
Partager sur d’autres sites
  • 0

Je dois avoir un problème de compréhension. Ta résolution ne correspond pas à l'énoncé tel que je le lis.

Les autres voient-ils la lueur de la lampe de la vérité depuis leur chambre ? Si oui, le disciple n°12 au 157e coup pourra affirmer avec justesse que tout le monde est déjà venu au minimum une fois.

Partager ce message


Lien à poster
Partager sur d’autres sites
  • 0

@akasolace  Je pense que ton raisonnement n'est pas correct, ou alors je ne le comprends pas.

J'aurais une autre stratégie à proposer.

Révélation

On décompose les jours en plages de longueur p:

Du jour 1 au jour p, la lampe ne sera allumée que par le prisonnier n°1. Les autres ne font rien.

Le jour p+1, on éteint la lampe (sauf si c'est le prisonnier n°2)

Du jour p+1 au jour 2p, la lampe ne sera allumée que par le prisonnier n°2. Les autres ne font rien.

...

Après extinction le jour i p +1, du jour i p+1 au jour (i+1)p, la lampe ne sera allumée que par le prisonnier n°i+1.

...

Après extinction le jour 32 p +1, du jour 32 p+1 au jour 33 p, la lampe ne sera allumée que par le prisonnier n°i+1.

Au jour 33 p+1 on considère que c'est à nouveau le jour 1, et on éteint la lampe (sauf si c'est le prisonnier n°1)

 

En rentrant dans sa chambre, chaque prisonnier note sur son carnet quand il sait qu'un prisonnier est bien passé.

Les différents prisonniers ne savent pas la même chose mais lorsque l'un d'eux sait que tous les autres sont passés, il affirme que tous les adeptes sont déjà venus. Ça paraît long, mais sans risque.

Le tout est de choisir la valeur adaptée pour p.

 

figure_1.thumb.png.a3270c0af91c3708a162e040381473cf.png

Sur l'exemple on a une victoire en 3522 jours pour une longueur de plage p=109.

En gros choisir p=100 pour une victoire autour de 4000 jours.

Partager ce message


Lien à poster
Partager sur d’autres sites
  • 0

@ribi  hello 2 things:

 

1) L' intitulé précise 

Quote

Ce fichier ne peut évidemment pas être utilisé pour définir une stratégie

 

je pense donc que ton approche ne peut pas être utilisée

 

2) tu dis que mon raisonement n'est pas correcte. Pourrais-tu stp me donner plus de détail? En fait je pense que tu as raison car en cherchant sur google j'ai trouvé un papier sur le sujet   https://sites.math.washington.edu/~morrow/336_11/papers/yisong.pdf   .  Il semblerait que mon approche ressemble a 3.4.4  "Single Counter Protocol with Dynamic Assignement" néanmoins eux font l'inverse de moi durant la phase 3

Quote

Prisoners who saw an ON bulb in Stage I do nothing.

alors que moi je fais Prisoners who saw an OFF bulb in Stage I do nothing.

 

mais j'avoue ne pas comprendre car pour moi ceux qui sont compté durant la phase 1 sont ceux qui ont vue la lamp OFF pas ON.  Je dois encore y réfléchir ... Est-ce que c'est l'erreur que tu avais détecter dans mon raisonement si oui j'aimerais bien des explications 🙂

 

Des que j'ai le temps je vais essayer de programmer cete approche pour voir si elle marche ... si elle marche j'essayerai de comprendre pourquoi ...

Partager ce message


Lien à poster
Partager sur d’autres sites
  • 0

1) Ce point est nul est non avenu. On peut remplacer le fichier donné par n'importe lequel tiré aléatoirement :

figure_1.thumb.png.8daec61e3d533487603f3fd7d32f3f27.png

Statistiquement, presque n'importe quel tirage aléatoire marche avec ma stratégie.

Celui-ci donne encore p=109 comme optimal en 3546 jours.

Je pense que le 109 est une coïncidence. Je relance avec un autre tirage aléatoire.

Je trouve p=85 optimal en 2798 jours...

Donc je maintiens, en gros p=100 a de bonnes chances de donner une victoire au bout de 4000 jours (confinement un peu long).

 

2) je pense qu'il s'agissait simplement d'un problème de compréhension de ma part, dû à la répétition de "étape 2" de " n n" derrière jour.

C'est normal que tu aies tout inversé par rapport à l'article. On peut inverser éteint et allumé, si c'est systématique, tu dois avoir raison.

Cette méthode est bien meilleure que la mienne, que j'ai improvisé, mais il me semble que tu perds inutilement du temps. Le prisonnier du jour n peut laisser la lumière allumée s'il n'est passé qu'une seule fois et n'a pas été comptabilisé, ce qui gagne du temps éventuellement.

 

Partager ce message


Lien à poster
Partager sur d’autres sites
  • 0

Sans réponse de l'auteur, ce sujet sera suspendu d'ici quelques jours

 

Ceci est une réponse automatique due à une absence de nouvelles de l'auteur de l'énigme

Partager ce message


Lien à poster
Partager sur d’autres sites
  • 0

@Cybero Donc concernant cette énigme la méthode optimal et qui est sûr de fonctionner est bien celle décrite plus haute appellée "double counter strategy" dans la litérature. 

Le premier adepte qui rentre 2 fois dans la pièce est désigné comme compteur.

Dans le cas ou n est très important il existe d'autre stratégies avec une espérance qui converge vers 1 très rapidement et qui pourraient donc être considérées ....

Partager ce message


Lien à poster
Partager sur d’autres sites

Créer un compte ou se connecter pour commenter

Vous devez être membre afin de pouvoir déposer un commentaire

Créer un compte

Créez un compte sur notre communauté. C’est facile !

Créer un nouveau compte

Se connecter

Vous avez déjà un compte ? Connectez-vous ici.

Connectez-vous maintenant

  • En ligne récemment   0 membre est en ligne

    Aucun utilisateur enregistré regarde cette page.

×
×
  • Créer...

Information importante

En utilisant ce site, vous acceptez notre Politique de confidentialité et nos Conditions d’utilisation
Nous avons placé des cookies sur votre appareil pour aider à améliorer ce site. Vous pouvez choisir d’ajuster vos paramètres de cookie, sinon nous supposerons que vous êtes d’accord pour continuer.