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+++
Salut
Beh il y en a 100 et 2 types de couleur, 50 y survivent.
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+++
C'est une vesion simplifiée du cas proposé par mmy ici : http://forums.futura-sciences.com/thread126696.htmlEnvoyé par spi100
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
Annulé par l'auteur qui ferait mieux de lire tous les messages avant de poster !
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+++
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+++
Ben on en sacrifie juste un, au pire, le premier... Après, le second est fixé sur sa couleur.
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+++
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
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+++
Le second n'a pas le droit de dire : même couleur que mon voisin ?
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+++
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
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 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 à 09h31.
GCS/S s: a C++ DI++>+++ UL++A++HIS++$ P++>+++$ E+>++$ W+>++$ N+ Y+ e++++ t+++ y+++
Parmi les prisonniers que voit la premierre personne... donc :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 ?
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+++
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" ?
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+++
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é...
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.
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.
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%.
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+++
C'est ce que j'avais supposé. Ca ne change donc pas ce que j'ai dit.
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+++
La somme, c'est 100.
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+++
