L’énigme de dictateur et de bouteilles de vin est un problème célèbre de logique. Un dictateur doit découvrir quelle bouteille, parmi les 1000 en sa possession, a été empoisonnée par un tueur. Pour ce faire, il n’a que 24 heures et peut utiliser 10 prisonniers condamnés à mort comme dégustations. La seule certitude qu’il a est qu’une seule goutte de vin empoisonné suffit à tuer un adulte. Comment trouverez-vous exactement la bouteille contaminée?
Cette énigme n’est pas seulement un jeu logique: c’est un exemple de Tests de groupeune technique pour individualiser Rapidement un élément défectueux dans un très grand groupe. Né dans le domaine médical, cette procédure est toujours utilisée aujourd’hui dans des secteurs tels que les télécommunications et le cybersécurité. Dans cet article, nous voyons quelle était la solution utilisée par le dictateur et comment cette stratégie s’applique Problèmes réels.
L’énigme du dictateur et des bouteilles de vin
La situation est la suivante: un cruel dictateur Il a organisé une grande fête dans son pays et, pour l’occasion, il a obtenu 1000 bouteilles de vin Précieux. On découvre cependant qu’un meurtrier se faufile dans les caves et a un empoisonné Et une seule des bouteilles. Le poison injecté par le meurtrier est incolore, sans odeur et sans symptômes jusqu’à la mort, qui arrive parmi les 10 et 15 heures plus tard Ingestion. Il n’y a aucun moyen d’identifier la bouteille contaminée si elle ne le fait pas boire à quelqu’un et une seule goutte de poison est suffisante pour tuer une personne adulte.
Le dictateur a 10 prisonniers condamné à mort et décide de les utiliser pour Testez le vin. Sa première idée est de diviser les bouteilles en 10 groupes de 100 et de faire condamner chacun une goutte de chaque bouteille de la boisson de groupe. Ainsi, les premiers condamnés buveraient 100 gouttes prises de 1 à 100 bouteilles, les 100 secondes de 101 à 200 bouteilles, les 100 troisième gouttes avec 201-300 bouteilles et ainsi de suite. À la mort de l’un des condamnés, le dictateur se débarrassera des 100 bouteilles à partir desquelles il a bu et pourra utiliser les 900 restants.
Le dictateur, cependant, aimerait économiser encore plus de bouteilles. Un conseiller de confiance intervient alors qui suggère une solution pour Trouvez exactement la bouteille empoisonnée. Voyons ce que c’est!
La solution: utilisez le code binaire
Pour comprendre la solution du réalisateur, nous devons penser comment les ordinateurs, c’est-à-dire système binaire. Contrairement au système décimal, que nous utilisons tous les jours et est basé sur dix chiffres (de 0 à 9), le système binaire utilise uniquement sur deux chiffres: 0 et 1.
Essayons de décrire notre problème en utilisant uniquement 0 et 1, à partir des condamnés. Chacun d’eux peut faire deux actions: boire ou Ne boive pas d’une bouteille. Ainsi, nous pouvons représenter leurs actions avec un 1 (boire de la bouteille) ou un 0 (ne boit pas de la bouteille). Regardons les bouteilles maintenant.
De nombreuses bouteilles utilisant le système binaire. Dans le système décimalce que nous avons l’habitude d’utiliser, chacun position correspond à un autre Pouvoir de 10: la bonne figure correspond à 100 (c’est-à-dire 1, les unités), alors il y en a 101 (c’est-à-dire les dizaines), puis 102 (c’est-à-dire des centaines) et ainsi de suite, augmentant progressivement l’exposant d’un. Là chiffre (de 0 à 9) que nous lisons dans chaque position nous dit Combien de fois Nous devons considérer que pouvoir. Par exemple, le numéro 34 est composé de 4 fois 100 c’est-à-dire 4 · 1 = 4 et 3 fois 101 c’est 3 · 10 = 30. Si nous ajoutons 30 et 4, nous obtenons 34.
Pour écrire un numéro dans tracesnous pensons d’une manière similaire, mais le Pouvoirs de 2pas 10. Dans ce cas, la figure la plus droite correspond à 20 (c’est-à-dire 1), sur sa gauche, nous avons 21 (c’est-à-dire 2), puis 22 (c’est-à-dire 4) et ainsi de suite. Ici aussi le chiffre que nous lisons dans chaque position nous dit combien de fois nous devons considérer ce pouvoir, mais dans ce cas, nous n’avons que deux possibilités, c’est-à-dire 0 (N’utilisez pas ce pouvoir) e 1 (utiliser).
Reprendre le numéro 34sur la piste, il est fabriqué par: 0 fois 20c’est 0 · 1 = 0; 1 fois 21 c’est 1 · 2 = 2; 0 fois 22c’est 0 · 4 = 0; 0 fois 23c’est 0 · 8 = 0; 0 fois 24c’est 0 · 16 = 0; 1 fois 25c’est 1 · 32 = 32. En assemblant tout, nous avons 34 écrits en piste est 100010. En fait, si nous ajoutons 32 + 2, nous obtenons 34.
Nous étiquetons puis les bouteilles en piste. Sur les étiquettes, nous verrons donc les nombres de 1 (numéro 1) à 1111101000 (numéro 1000).
À ce stade, nous prenons les dix condamnés et les avons mis en ligne. Chaque condamné représentera un Pouvoir de 2. Le plus condamné à droite sera 20 (c’est-à-dire 1), celui de plus gauche 29 (c’est-à-dire 512).
Maintenant, nous prenons chaque bouteille et lisons l’étiquette avec le numéro dans le code binaire écrit ci-dessus. Donnons alors une goutte Boire à tous condamné trouvé dans le positions dans lequel Il y a un « 1 » (qui correspondait à « boire »). Par exemple: la bouteille numéro 4 aura 00000000100 (4 en piste) écrit sur l’étiquette. Ainsi, une goutte de ce vin au troisième condamné de la droite sera faite pour boire, car il y a une position de 1 en troisième. Pour la bouteille 295 (0100100111), nous donnerons un verre (à partir de la droite) aux trois premiers, dans les sixième et neuvième condamnés.
Fait ça, ce sera suffisant pour nous attendez jusqu’à 20 heures e Voir quels ont condamné ils meurent. S’ils sont morts, par exemple les condamnés en position 2 et 6, nous saurions que la bouteille empoisonnée est celle qui a écrit 0000100010 sur l’étiquette, c’est la bouteille numéro 34.
En utilisant cette stratégie, nous serons en mesure de Obtenez le numéro exactement de bouteille empoisonnée Et nous pourrons donc sauver l’autre 999.
Comment trouver les « erreurs » dans un grand groupe: quel est le Tests de groupe
Ce type de raisonnement est un exemple de ce qu’on appelle Tests de groupeou test de groupe, une procédure dans laquelle vous essayez de Identifier les éléments « défectueux » (Dans notre cas, la bouteille empoisonnée) dans un très grand ensemble. Habituellement, ce type de test se fait avec plus d’un élément « défectueux » et devient par conséquent plus complexe que l’exemple que nous avons signalé ici.
La première formulation des tests de groupe remonte à 1943, pendant la Seconde Guerre mondiale. Il a été inventé pour résoudre un problème critique pendant le levier: test des dizaines de milliers de recruter pour syphilis. Pour réduire le nombre de tests nécessaires, les échantillons de sérum de nombreux soldats ont été collectés et l’ensemble du groupe a été analysé, au lieu de tester chaque recrue individuellement. Le principe de test de groupe a également trouvé une application dans d’autres domaines. Par exemple, il est utilisé pour gérer le Partage des canaux entre les appareils de radio. Également dans le domaine des technologies de l’information et le cybersécurité Une approche similaire est utilisée pour découvrir des erreurs ou des vulnérabilités dans de grands systèmes complexes.
Le principe à la base est toujours le même: minimiser le nombre de tests nécessaires en utilisant la meilleure stratégie, comme l’a fait le conseiller avec les bouteilles de vin.