akasolace

@ribi alors moi c'est l'inverse je trouve E(4) mais je ne trouve pas E(3) ! comment fais-tu pour E(3) ?

pour n= 1, une seule case donc S(1) = 1 et E(1) = 1 pour n=2, on vise d'abord une case, puis ensuite la même pour etre sur de gagner (soit on tue l'insecte la premiere ois ou alors la deuxieme s'il était sur l'autre case) S(2) = 2 E(2) = 1*1/2 + 2*1/2 = 1.5

Soit n cases successives sur lesquelles un insecte microscopique se déplace. Une personne qui n'arrive pas à voir l'insecte - car trop petit, veut éliminer l'insecte. S'il y parvient, il le saura, car l'insecte dégagera alors une odeur nauséabonde.La personne peut pulvériser l'insecticide sur une case a la fois, alors: - soit l'insecte meurt - soit il se déplace vers une case adjacente de manière aléatoire La personne adopte une stratégie S(n) lui permettant de minimiser la quantité d'insecticide a répandre - noté que S(n) ne minimise pas forcéement l'espérance !Soit E(n) le nombre moyen de doses nécessaires pour éliminer l'insecteSachant que E(1)=1, E(2)=1.5, E(3)=1.5 et E(4)=2.3125, que vaut E(5) ?Précision : le calcul de E(n) sera basé uniquement sur tous les trajets possibles de l'insecte exactement S(n) déplacements, comme s'il se déplaçait toujours S(n) fois, qu'il ait été pulvérisé avec de l'insecticide ou non.

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

@ribi hello 2 things: 1) L' intitulé précise 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 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 ...

@ribi oui @kinder est correct seul celui qui entre dans la chambre voit si la lumière est allumée ou non

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

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

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 ?"