Problème concernant les prisonniers et les casquettes, dont la couleur doit être déterminée
Récréation / / December 31, 2020
Le système de fermeture voit toutes les majuscules, mais ne peut dire que «noir» ou «blanc», tout en informant simultanément tout le monde des informations cachées. Les prisonniers ne connaissent pas le nombre total de bonnets noirs et blancs, il y a plus de deux options possibles. Mais ils sont limités à seulement deux versions en ce qui concerne le concept de parité: le nombre peut être pair ou impair.
La clé pour résoudre le problème est la suivante: les prisonniers conviennent que le premier intervenant dira, par exemple, "noir", s'il voit un nombre impair de casquettes noires devant, et "blanches" s'il voit un nombre pair de casquettes noires casquettes.
Regardons l'exemple de l'image ci-dessus. Le plus grand prisonnier n ° 1 voit trois casquettes noires devant lui. Il parle «noir» à haute voix. Cela donne à tout le monde l'information qu'il y a un nombre impair de casquettes noires à venir. Le premier prisonnier a fait une erreur avec la couleur de sa casquette, mais ce n'est pas effrayant: une fois qu'il est autorisé à répondre incorrectement.
La prisonnière n ° 2 voit un nombre impair de casquettes noires devant elle. Elle comprend qu'elle est blanche et répond correctement. Le prisonnier n ° 3 voit un nombre pair de bonnets noirs et suppose qu'il porte un bonnet noir que les deux premiers captifs ont vu.
La prisonnière n ° 4 entend la réponse et se rend compte qu'elle devrait chercher un nombre pair de casquettes noires, car il y en avait une noire derrière son dos, mais elle n'en voit qu'une devant elle et conclut que sa casquette est noire. Les prisonniers n ° 5 à 9 recherchent un nombre impair de bonnets noirs, qu'ils voient, tout en se rendant compte qu'ils portent des bonnets blancs. Le tour vient au dixième prisonnier. Si le captif n ° 9 a vu un nombre impair de casquettes noires, cela signifie qu'une seule chose: le captif n ° 10 a un capuchon noir.
C'est ainsi que cet algorithme fonctionnerait pour n'importe quel ensemble d'enjoliveurs. Pour le premier participant, la probabilité d'une réponse incorrecte est de 50%, mais les informations sur la parité paire-impaire, qu'il donnera, permettront au reste des captifs de deviner la couleur de leur casquette.
Chaque répondant commencera à évaluer le nombre de plafonds pairs et impairs à venir. Si le nombre calculé dans son esprit ne coïncide pas avec ce qu'il voit, alors sa casquette est de la même couleur. À chaque fois, dans un tel cas, le répondant suivant prend en compte le fait que la parité des plafonds restants a maintenant changé.
Ce puzzle est la traduction d'une vidéo TED-Ed.