énigme des prisonniers

[spi100]

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

[invite0f34eb03]

Salut

Beh il y en a 100 et 2 types de couleur, 50 y survivent.

[spi100]

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

[yat]

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

[A voir en vidéo sur Futura]

[invite8241b23e]

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

[invité576543]

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

[spi100]

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.

[spi100]

Oui, effectivement c'est un cas particulier de l'énigme de mmy, je ne l'avais pas vue.

[invite8241b23e]

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.

[spi100]

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.

[invite8ef897e4]

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

[spi100]

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

[invité576543]

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

[spi100]

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.

[yat]

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 :

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 ?

[spi100]

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.

[invitebd686fd6]

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.

[invite8241b23e]

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 ?

[spi100]

non, il n'a le droit de dire que "bleu" ou "rouge"

[yat]

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 ?