Répondre à la discussion
Affichage des résultats 1 à 17 sur 17

Problème des chapeaux (facile)



  1. #1
    sh3ll

    Problème des chapeaux (facile)


    ------

    On prévient les prisonniers d'une prison qu'on va leur attribuer à chacun (au hasard) soit un chapeau blanc soit un chapeau noir. On leur dit aussi qu'on les mettra en ligne devant la porte de sortie et qu'on les questionnera chacun leur tour (en partant du dernier pour arriver jusqu'au premier) : si le prisonnier interrogé donne la couleur de son chapeau (qu'il ne voit pas bien entendu) on le libère.
    Chaque prisonnier voit tous les chapeaux devant lui mais ne voit pas le sien.

    => On leur laisse du temps pour mettre au point une stratégie.

    => Quelle est la stratégie à employer pour faire sortir le maximum de prisonniers ?

    -----

  2. Publicité
  3. #2
    Syracuse_66

    Re : Problème des chapeaux (facile)

    Le dernier compte le nombre total de chapeaux blancs et de chapeaux noirs et le dit au voisin qui fait de même et pourra ainsi déduire la couleur de son chapeau.
    On sauve ainsi 99 prisonniers, le dernier a une chance sur 3 de survivre ^^

  4. #3
    piwi

    Re : Problème des chapeaux (facile)

    J'ai quelque chose de simpliste mais bon c'est une première approche.
    Le premier donne la couleur du chapeau de devant. Il y a 1/2 chances que ça soit aussi la sienne.
    Le gars de devant donne la couleur de chapeau qu'il a entendu donc lui il a 100% de chances de sortir.
    On reprend le cycle devant.
    Du coup on a 50% des personnes qui sont certaines de sortir et 50% des personnes qui ont 1/2 chances de sortir.
    Y a 75% des prisonniers qui sortent normalement.

    Bon c'est sommaire, on peut peut être faire mieux.
    Cordialement,
    piwi

  5. #4
    humanino

    Re : Problème des chapeaux (facile)

    Bonjour,

    il existe une strategie qui permet de liberer de facon certaines tous les prisonniers sauf 1.
     Cliquez pour afficher
    "Puisque toute ces choses nous depassent, feignons de les avoir organisees"

  6. A voir en vidéo sur Futura
  7. #5
    piwi

    Re : Problème des chapeaux (facile)

    Oui bon mais je ne pense pas que les regles autorisent à dire autre chose qu'une couleur sinon effectivement l'info remonte facilement.

  8. #6
    sh3ll

    Re : Problème des chapeaux (facile)

    On ne peut pas dire autre chose que "blanc" ou "noir"...
    Pas d'indice de sonorité ou de mouvements, juste l'information blanc ou noir...
    EDIT : Ta réponse n'est pas très très claire, humanino...je vois l'idée (puisque je connais la solution) mais je pense que pour ceux qui veulent la solution, il sera difficile pour eux de te comprendre

    N'oubliez pas qu'ils ont le droit de se réunir avant pour mettre une stratégie en place.
    Dernière modification par sh3ll ; 06/07/2007 à 18h29.

  9. Publicité
  10. #7
    humanino

    Re : Problème des chapeaux (facile)

    Ouais je suis jamais clair de toute facon, c'est pas grave
    Si quelqu'un veut prendre le temps d'expliquer en longueur...
    "Puisque toute ces choses nous depassent, feignons de les avoir organisees"

  11. #8
    kNz

    Re : Problème des chapeaux (facile)

    Citation Envoyé par humanino Voir le message
    Ouais je suis jamais clair de toute facon, c'est pas grave
    Si quelqu'un veut prendre le temps d'expliquer en longueur...
    Moi j't'ai trouvé assez clair
    Ils se réunissent avant et se disent que avoir un chapeau blanc correspond à 0 et un chapeau noir à 1.
    Le premier qui doit parler regarde les chapeaux des autres.
    Il compte le nombre de chapeaux blancs, il y en a B, et le nombre de chapeaux noirs, il y en a N.
    En tout il y a B+N+1 chapeaux.
    Il doit donner un renseignement qui renseigne sur la parité de N.
    Si N est pair, il annonce Noir, si N est impair il annonce Blanc.
    Bon lui son sort est déterminé par le hasard

    Maintenant n'importe quelle autre personne connaît sa couleur.
    Elle compte le nombre de chapeaux noirs et de chapeaux blancs qu'elle voit sauf celui du premier à avoir parler.
    • si le premier annonce Noir, il y a donc un nombre pair de chapeaux noirs, donc si la personne voit un nombre impair de chapeaux sans compter celui du premier à avoir parlé, elle a donc un chapeau noir. Si elle voit un nombre pair de chapeaux noirs, elle a un chapeau blanc.
    • si le premier annonce Blanc, il y a donc un nombre impair de chapeaux noirs, donc si la personne voit un nombre pair de chapeaux sans compter celui du premier à avoir parlé, elle a donc un chapeau noir. Si elle voit un nombre impair de chapeaux noirs, elle a un chapeau blanc.

  12. #9
    piwi

    Re : Problème des chapeaux (facile)

    Moi j'ai une amélioration de ma méthode:
    On considère les personnes par 4.
    Le premier donne la couleur dominante des trois autres devant. Il a lui même toujours 1/2 de sortir.
    Les trois autres. Si le premier voit les deux chapeaux devant lui de la couleur dominante il a tout intérêt à énoncer la couleur opposée. En effet il n'y a que 1/8 chances que tous les chapeaux soient de la même couleur. Il a donc 7/8 de sortir. S'il voit les deux couleurs devant lui il sait qu'il a la couleur dominante, il sort à tous les coups.
    Le second retire une info du devenir du premier il sort à tous les coups. Le dernier sort aussi à tous les coups.
    On a donc
    1/4+1/4+1/4x7/8+1/4x1/2. Ca donne à peu près 84% de chances de sortir.

    Je ne sais pas si l'on peut faire mieux avec cette méthode car il me semble que donner la couleur dominante de 5 chapeaux donne trop d'incertitude et ne permet aux personnes de décider autrement qu'au hasard. Je peux me tromper, c'est une intuition.

    EDIT: bon ben manifestement il y avait une meilleure méthode
    Cordialement,
    piwi

  13. #10
    piwi

    Re : Problème des chapeaux (facile)

    Remarquez que la méthode optimale suppose un nombre raisonnable de prisonniers pour que le dernier puisse les compter dans la file. Si il y a 1000 prisonniers à la queue leuleu c'est pas gagné.
    Alors que ma méthode est possible même si l'on a une infinité de prisonniers vu qu'elle ne repose pas sur un seul compteur mais sur des sous groupes

    Bon ok je vends ma soupe là

  14. #11
    piwi

    Re : Problème des chapeaux (facile)

    re edit.
    J'ai été un peu optimiste sur la proba conditionnelle...
    En fait ca ne marche pas mon truc. Il a une chance sur deux d'avoir un chapeau de la couleur dominante, point barre.

    En fait mon truc est tout pourri. Oubliez le!

    Cordialement,
    piwi

  15. #12
    cadors

    Re : Problème des chapeaux (facile)

    Ils doivent s'aligné devant l'entré un après l'autre tjrs par le centre, j'explique

    N = Noir B = Blanc | = porte


    le premier se place près de la porte
    le second derière le premier

    et le troisième est important si on a : N N| ou B B| il se place derrière les deux si on a N B il se place entre les deux donc on aura N N B ou N B B et on continue ainsi jusqu'à 100, tant qu'il n'y a qu'une couleur le prochain le place en dernier.

    au final on aura donc ... N N N N B B B B B B ...| chaque fois qu'un prisonnier vient se palcer il permet au précédent de connaître la couleur selon que le prisonnier se palce devant ou derrière ( le plaçant avec les noir ou avec les blanc )

    puis celui de devant revient au centre ( il sait déjà la couleur de sont chapeau du coup il permet au dernier de connaître sa couleur

    ceci permet de sauvé 100 % des prisonnier !!!

    Merci et Bonne fin de semaine !!

    oh et en passant ! il me semble improbable que tout les prisonniers soit de parfait logiciens alors cette méthode est idéale car elle pourrait être faite par des enfants !
    "Pourquoi est-ce les personnes qui en savent le moins qui en parle le plus ?"

  16. Publicité
  17. #13
    piwi

    Re : Problème des chapeaux (facile)

    Oui mais avec ta méthode ils s'organisent eux même ce qui signifie que tout le monde sait quel chapeau il a sur la tête avant de s'organiser
    Effectivement dans ce cas autant les libérer tous tout de suite!

    piwi

  18. #14
    kNz

    Re : Problème des chapeaux (facile)

    Oula j'sais pas pourquoi j'avais pas lu l'énoncé j'étais persuadé que chacun voyait tous les autres chapeaux. Il faut donc apporter une variante dans mon explication de la méthode de humanino : il faut que chacun mémorise la parité des chapeaux noirs qui étaient avant lui, c'est un peu plus dur

    Sinon cadors, je doute que les prisonniers se placent comme ils veulent

  19. #15
    sh3ll

    Re : Problème des chapeaux (facile)

    La réponse était effectivement celle sur la parité !
    Pour info, combien de temps as tu mis pour la trouver ?
    Moi j'ai mis 20 minutes (mais en prenant mon gouter en même temps )...
    Posez le à des non-mathématiciens et vous seriez surpris de voir que personne n'est capable de le resoudre alors qu'une fois la solution connue ce problème semble si simple ! ^^
    Bonne soirée

  20. #16
    humanino

    Re : Problème des chapeaux (facile)

    Citation Envoyé par sh3ll Voir le message
    Pour info, combien de temps as tu mis pour la trouver ?
    Je connaissais deja, pas exactement sous cette forme, mais la premiere fois qu'on me l'a pose j'ai du mettre 4 ou 5 minutes, pas tres longtemps. Mais bon, j'ai la prepa math loin derriere moi ca aide
    on rajeunie pas...
    "Puisque toute ces choses nous depassent, feignons de les avoir organisees"

  21. #17
    cadors

    Re : Problème des chapeaux (facile)

    Citation Envoyé par piwi Voir le message
    Oui mais avec ta méthode ils s'organisent eux même ce qui signifie que tout le monde sait quel chapeau il a sur la tête avant de s'organiser
    Effectivement dans ce cas autant les libérer tous tout de suite!

    piwi

    Non ! selon ma méthode ils ne connaisse pas la couleur de leur chapeau avant de s'organisé, il ne font que se placé chacun leur tour entre deux personne dont la couleur est différente du coup, il finisse par séparer les blancs des noirs et c'est cela qui leur permet de connaître la couleur de leur chapeau

    L'énigme dit :

    => On leur laisse du temps pour mettre au point une stratégie

    cela n'indique pas une limite de temps précise et une limite dans les stratégie utilisables, alors je crois qu'ils doivent utilisé cette stratégie ou alors s'aligner de la même manière le long d'un mur (comme dans la variante de cette énigme) afin de connaître leur couleur avant d'être placé en file, dans tout les cas je suis convaincu que 100% des prisonnier peuvent être sauvés !
    "Pourquoi est-ce les personnes qui en savent le moins qui en parle le plus ?"

Discussions similaires

  1. Problème facile
    Par Geb dans le forum Mathématiques du collège et du lycée
    Réponses: 5
    Dernier message: 29/12/2006, 18h14
  2. ouverture facile : encore des énigmes
    Par ahotep dans le forum Science ludique : la science en s'amusant
    Réponses: 2
    Dernier message: 28/09/2006, 09h59
  3. petit problème facile (et encore!)
    Par didj306style dans le forum Chimie
    Réponses: 9
    Dernier message: 01/03/2006, 14h53
  4. énigme des chapeaux
    Par stein_junior dans le forum Science ludique : la science en s'amusant
    Réponses: 21
    Dernier message: 15/12/2005, 18h11
  5. Si facile...
    Par S59 dans le forum Mathématiques du supérieur
    Réponses: 6
    Dernier message: 30/12/2004, 18h26