Répondre à la discussion
Page 1 sur 2 1 DernièreDernière
Affichage des résultats 1 à 30 sur 35

énigme des prisonniers



  1. #1
    spi100

    énigme des prisonniers


    ------

    Une variante de l'égnime des prisonniers:

    100 prisonniers portent un chapeau rouge ou bleu. Chaque prisonnier connait la couleur des chapeaux des autres mais pas la couleur du sien.
    Un bourreau demande alors à chacun la couleur de son chapeau. Si le prisonnier se trompe il est tué.

    Il existe une stratégie permettant d'en sauver au moins 99 ...

    -----
    GCS/S s: a C++ DI++>+++ UL++A++HIS++$ P++>+++$ E+>++$ W+>++$ N+ Y+ e++++ t+++ y+++

  2. Publicité
  3. #2
    kyusu

    Re : énigme des prisonniers

    Salut

    Beh il y en a 100 et 2 types de couleur, 50 y survivent.
    l'homme est comme un dipole RL;il s'oppose à tous changement.

  4. #3
    spi100

    Re : énigme des prisonniers

    si tu réponds au hasard mais il y a un moyen d'en sauver au moins 99 en répondant selon une certaine stratégie
    GCS/S s: a C++ DI++>+++ UL++A++HIS++$ P++>+++$ E+>++$ W+>++$ N+ Y+ e++++ t+++ y+++

  5. #4
    yat

    Re : énigme des prisonniers

    Citation Envoyé par spi100 Voir le message
    Une variante de l'égnime des prisonniers:

    100 prisonniers portent un chapeau rouge ou bleu. Chaque prisonnier connait la couleur des chapeaux des autres mais pas la couleur du sien.
    Un bourreau demande alors à chacun la couleur de son chapeau. Si le prisonnier se trompe il est tué.

    Il existe une stratégie permettant d'en sauver au moins 99 ...
    C'est une vesion simplifiée du cas proposé par mmy ici : http://forums.futura-sciences.com/thread126696.html

  6. #5
    benjy_star

    Re : énigme des prisonniers

    Salut !

    Il suffit de dire : la même couleur que mon voisin, comme ça on est fixé dès le second. Qui dire : même couleur que mon voisin/autre couleur que mon voisin. Et ainsi de suite...

    J'ai bon

  7. A voir en vidéo sur Futura
  8. #6
    invité576543
    Invité

    Re : énigme des prisonniers

    Annulé par l'auteur qui ferait mieux de lire tous les messages avant de poster !

  9. Publicité
  10. #7
    spi100

    Re : énigme des prisonniers

    Désolé Benjy mais il y a une chance sur deux que la couleur de ton voisin soit la même que la tienne.

    Je donne une indiquation : si avec 100 prisonniers il y a une stratégie permettant d'en sauver au moins 99, cette stratégie ne fonctionne plus du tout pour 667 prisonniers.
    GCS/S s: a C++ DI++>+++ UL++A++HIS++$ P++>+++$ E+>++$ W+>++$ N+ Y+ e++++ t+++ y+++

  11. #8
    spi100

    Re : énigme des prisonniers

    Oui, effectivement c'est un cas particulier de l'énigme de mmy, je ne l'avais pas vue.
    GCS/S s: a C++ DI++>+++ UL++A++HIS++$ P++>+++$ E+>++$ W+>++$ N+ Y+ e++++ t+++ y+++

  12. #9
    benjy_star

    Re : énigme des prisonniers

    Citation Envoyé par spi100 Voir le message
    Désolé Benjy mais il y a une chance sur deux que la couleur de ton voisin soit la même que la tienne.
    Ben on en sacrifie juste un, au pire, le premier... Après, le second est fixé sur sa couleur.

  13. #10
    spi100

    Re : énigme des prisonniers

    Si le second dit sa couleur, il rompt la chaine. Pour ne pas rompre la chaine il doit donner la couleur du troisième, mais rien ne guarantit que ce soit sa couleur.
    GCS/S s: a C++ DI++>+++ UL++A++HIS++$ P++>+++$ E+>++$ W+>++$ N+ Y+ e++++ t+++ y+++

  14. #11
    humanino

    Re : énigme des prisonniers

    On a deja la reponse ou pas ?
    Si l'on assigne 0 et 1 aux deux couleurs, le premier peut donner le residu modulo 2 de la somme de toutes les couleurs. Il a une chance sur deux de survivre, mais tous les autres sont sauves, certainement. Et cela ne depend pas du nombre de prisonniers
    "Puisque toute ces choses nous depassent, feignons de les avoir organisees"

  15. #12
    spi100

    Re : énigme des prisonniers

    Ca dépend plus ou moins du nombre de personnes...

    Connaitre le résidu du modulo n'apporte rien s'il est le même pour les deux groupes
    GCS/S s: a C++ DI++>+++ UL++A++HIS++$ P++>+++$ E+>++$ W+>++$ N+ Y+ e++++ t+++ y+++

  16. Publicité
  17. #13
    benjy_star

    Re : énigme des prisonniers

    Citation Envoyé par spi100 Voir le message
    Si le second dit sa couleur, il rompt la chaine. Pour ne pas rompre la chaine il doit donner la couleur du troisième, mais rien ne guarantit que ce soit sa couleur.
    Le second n'a pas le droit de dire : même couleur que mon voisin ?

  18. #14
    spi100

    Re : énigme des prisonniers

    non, il n'a le droit de dire que "bleu" ou "rouge"
    GCS/S s: a C++ DI++>+++ UL++A++HIS++$ P++>+++$ E+>++$ W+>++$ N+ Y+ e++++ t+++ y+++

  19. #15
    invité576543
    Invité

    Re : énigme des prisonniers

    Citation Envoyé par spi100 Voir le message
    Ca dépend plus ou moins du nombre de personnes...
    Connaitre le résidu du modulo n'apporte rien s'il est le même pour les deux groupes
    Padak. La réponse de humanino est correcte (une fois la précision omise réintégrée, "la somme de toutes les couleurs qu'il voit"), d'ailleurs c'est la même réponse que la solution générale donnée dans l'autre fil.

    Cordialement

  20. #16
    yat

    Re : énigme des prisonniers

    Citation Envoyé par benjy_star Voir le message
    Le second n'a pas le droit de dire : même couleur que mon voisin ?
    Même si c'était le cas... je vois pas vraiment l'intérêt. En quoi ça va permettre à plus de la moitié des prisonniers de trouver ?

  21. #17
    spi100

    Re : énigme des prisonniers

    Je n'ai peut être pas la réponse complète alors. Voilà la solution que j'avais :

    La première personne voit 99 personnes. Il y a forcemment un groupe qui a un nombre pair de prisonniers et un autre qui a un nombre impair de prisonniers .

    La personne interrogée est forcemment dans le groupe impair. Il ne reste plus qu'à savoir à quelles couleurs correspondent les groupes impair et pair. Elle essaie une couleur. Elle a un chance sur deux de se tromper.

    La deuxième personne, compte le nombre de personne qui ont la même couleur que le premier. Si ce nombre est pair, elle en déduit qu'elle est dans l'autre groupe, sinon elle est dans le même groupe que le premier.

    Et ainsi de suite.
    Mais cette solution ne marche pas pour 101 personnes, car alors les deux groupes dénombrés par la personne sont tous deux pairs.
    Dernière modification par spi100 ; 02/03/2007 à 10h31.
    GCS/S s: a C++ DI++>+++ UL++A++HIS++$ P++>+++$ E+>++$ W+>++$ N+ Y+ e++++ t+++ y+++

  22. #18
    yat

    Re : énigme des prisonniers

    Citation Envoyé par spi100 Voir le message
    Je n'ai peut être pas la réponse complète alors. Voilà la solution que j'avais :

    La première personne voit 99 personnes. Il y a forcemment un groupe qui a un nombre pair de prisonniers et un autre qui a un nombre impair de prisonniers .
    Parmi les prisonniers que voit la premierre personne... donc :
    Citation Envoyé par spi100 Voir le message
    La personne interrogée est forcemment dans le groupe impair.
    La personne interrogée, c'est toujours la première personne dont on parlait au dessus ? Dans ce cas elle n'est pas dans un des deux groupes. Et sinon, pourquoi serait-elle forcément dans le groupe impair ?

  23. Publicité
  24. #19
    spi100

    Re : énigme des prisonniers

    essaie avec 3 personnes : P1-B, P2-R, P3-B, P4-R ( B pour bleu, R pour rouge)

    Les prisonniers conviennent de compter le nombre de personnes qu'ils voient et de donner systématiquement la couleur du groupe impair.

    P1 est interrogée, elle compte 2 R et 1 B. Elle donne la coleur du groupe impair : B. Soit elle B, elle reste en vie, soit elle est rouge, elle meurt.

    P2 sait que P1 est en vie et qu'elle a donné la couleur du groupe impair. P2 compte 2 B et 1 un R. Elle est en déduit qu'elle est R.
    GCS/S s: a C++ DI++>+++ UL++A++HIS++$ P++>+++$ E+>++$ W+>++$ N+ Y+ e++++ t+++ y+++

  25. #20
    yat

    Re : énigme des prisonniers

    Citation Envoyé par spi100 Voir le message
    essaie avec 3 personnes : P1-B, P2-R, P3-B, P4-R ( B pour bleu, R pour rouge)

    Les prisonniers conviennent de compter le nombre de personnes qu'ils voient et de donner systématiquement la couleur du groupe impair.

    P1 est interrogée, elle compte 2 R et 1 B. Elle donne la coleur du groupe impair : B. Soit elle B, elle reste en vie, soit elle est rouge, elle meurt.

    P2 sait que P1 est en vie et qu'elle a donné la couleur du groupe impair. P2 compte 2 B et 1 un R. Elle est en déduit qu'elle est R.
    J'ai du mal à faire le lien avec les explications de ton post précédent, mais je crois que cette fois j'ai compris. Ca revient en gros à la solution de mmy/humanino, mais prise dans l'autre sens : la solution consiste à ce que le premier donne une information binaire au reste du groupe concernant la parité du nombre de chapeaux d'une couleur donnée. Mais là, en l'occurence, au lieu de donner la parité d'une couleur définie à l'avance, tu donnes la couleur du groupe impair. Donc au final, la seule différence est que tu as besoin qu'il y ait exactement un groupe impair, et donc que le nombre de prisonniers total soit pair.

    Comme c'est le cas, ça marche aussi

    P.S : Ca voulait dire quoi, "La personne interrogée est forcemment dans le groupe impair. Il ne reste plus qu'à savoir à quelles couleurs correspondent les groupes impair et pair" ?

  26. #21
    spi100

    Re : énigme des prisonniers

    Citation Envoyé par yat Voir le message
    P.S : Ca voulait dire quoi, "La personne interrogée est forcemment dans le groupe impair. Il ne reste plus qu'à savoir à quelles couleurs correspondent les groupes impair et pair" ?
    La personne interrogée est forcemment de la même couleur que les personnes du groupe impair.
    GCS/S s: a C++ DI++>+++ UL++A++HIS++$ P++>+++$ E+>++$ W+>++$ N+ Y+ e++++ t+++ y+++

  27. #22
    benjy_star

    Re : énigme des prisonniers

    Citation Envoyé par yat Voir le message
    Même si c'était le cas... je vois pas vraiment l'intérêt. En quoi ça va permettre à plus de la moitié des prisonniers de trouver ?
    Je ferme après la parenthèse : s'il peut voir le chapeau du voisin1, qui dit "autre couleur que mon voisin2", comme voisin1 sera sauvé, voisin2 saura qu'il a l'autre couleur. Comme il connait les deux, c'est gagné...

  28. #23
    halman

    Re : énigme des prisonniers

    Les prisonniers demandent à leurs voisins la couleur de leur chapeau.

    Le dernier n'a pas de chance, il reste seul, il ne peut demander à personne la couleur de son chapeau et a une chance sur deux de se tromper.

  29. #24
    yat

    Re : énigme des prisonniers

    Citation Envoyé par spi100 Voir le message
    La personne interrogée est forcemment de la même couleur que les personnes du groupe impair.
    Mais quelle personne interrogée ? Certainement pas la première, quel que soit ce qu'elle voit, son chapeau peut être rouge ou bleu...

    Je suppose que tu veux dire que si la premiere personne a gagné, alors son chapeau est de la même couleur que le groupe qu'elle voyait impair, ce qui veut dire qu'il y a un nombre pair de chapeaux rouges et un nombre pair de chapeaux bleus. Avec cette information, tous les autres prisonniers savent donc que leur chapeau est de la couleur du groupe qu'ils voient impair.

    Mais dans le cas contraire, si la première personne perd, alors on a deux groupes impairs, et chaque personne a un chapeau de la couleur du groupe qu'il voit pair.

  30. Publicité
  31. #25
    yat

    Re : énigme des prisonniers

    Citation Envoyé par benjy_star Voir le message
    Je ferme après la parenthèse : s'il peut voir le chapeau du voisin1, qui dit "autre couleur que mon voisin2", comme voisin1 sera sauvé, voisin2 saura qu'il a l'autre couleur. Comme il connait les deux, c'est gagné...
    Ce qui ne marche que par paires... du coup, le deuxième de chaque paire est sur d'être sauvé, mais le premier a toujours une chance sur deux. On a ici un rendement de 75%.

  32. #26
    spi100

    Re : énigme des prisonniers

    Citation Envoyé par yat Voir le message
    Mais dans le cas contraire, si la première personne perd, alors on a deux groupes impairs, et chaque personne a un chapeau de la couleur du groupe qu'il voit pair.
    En fait, je ne l'ai pas précisé quand une personne est tuée, elle reste dans le groupe. Elle n'en sort pas.
    GCS/S s: a C++ DI++>+++ UL++A++HIS++$ P++>+++$ E+>++$ W+>++$ N+ Y+ e++++ t+++ y+++

  33. #27
    yat

    Re : énigme des prisonniers

    Citation Envoyé par spi100 Voir le message
    En fait, je ne l'ai pas précisé quand une personne est tuée, elle reste dans le groupe. Elle n'en sort pas.
    C'est ce que j'avais supposé. Ca ne change donc pas ce que j'ai dit.

  34. #28
    spi100

    Re : énigme des prisonniers

    Citation Envoyé par yat Voir le message
    Mais dans le cas contraire, si la première personne perd, alors on a deux groupes impairs, et chaque personne a un chapeau de la couleur du groupe qu'il voit pair.
    Tu ne peux pas avoir deux groupes impairs, puisque dans ce cas la somme serait paire et ce n'est pas le cas de 99.
    GCS/S s: a C++ DI++>+++ UL++A++HIS++$ P++>+++$ E+>++$ W+>++$ N+ Y+ e++++ t+++ y+++

  35. #29
    yat

    Re : énigme des prisonniers

    Citation Envoyé par spi100 Voir le message
    Tu ne peux pas avoir deux groupes impairs, puisque dans ce cas la somme serait paire.
    La somme, c'est 100.

  36. #30
    spi100

    Re : énigme des prisonniers

    Tu as 100 personnes. Les deux groupes sont forcemment pairs. Mainteant la personne interrogée voit 99 personnes, un groupe pair et un groupe impair.
    GCS/S s: a C++ DI++>+++ UL++A++HIS++$ P++>+++$ E+>++$ W+>++$ N+ Y+ e++++ t+++ y+++

Sur le même thème :

Page 1 sur 2 1 DernièreDernière

Discussions similaires

  1. Devinette, 100 Prisonniers
    Par siris dans le forum Science ludique : la science en s'amusant
    Réponses: 111
    Dernier message: 27/06/2007, 10h11
  2. Enigme des prisonniers
    Par drwriggles dans le forum Science ludique : la science en s'amusant
    Réponses: 20
    Dernier message: 12/02/2007, 22h03
  3. L'énigme des prisonniers
    Par g_h dans le forum Science ludique : la science en s'amusant
    Réponses: 6
    Dernier message: 15/01/2007, 17h53
  4. Prisonniers du temps
    Par zapman dans le forum Archéologie
    Réponses: 3
    Dernier message: 10/04/2005, 00h15
  5. Proba conditionnelle : les 3 prisonniers
    Par jcm dans le forum Mathématiques du supérieur
    Réponses: 10
    Dernier message: 19/12/2004, 12h49