Logo Zéphyrnet

Comment le lieutenant Uhura de Star Trek a surmonté les obstacles astronomiques

Date :

Nos tâche de casse-tête le mois dernier était de sauver un Star Trek groupe de surface de huit dirigé par le Entreprise Chargée de communication Lieutenant Uhura (joué par feu Nichelle Nichols). L'équipage est emprisonné par une race extraterrestre, les Catenati, sur une planète du Collier Nébuleuse. Pour s'en sortir, ils doivent maximiser leur probabilité d'accomplir une tâche qui, au premier abord, ne semble offrir qu'une faible probabilité de réussite.

L'équipage de huit personnes est informé de la tâche tout en étant temporairement détenu dans une salle commune où ils sont libres de communiquer et d'élaborer des stratégies. Dans quelques heures, ils seront conduits, un par un, dans une salle appelée la chambre de la roulette. Cette pièce dispose de huit boutons disposés en ligne, chacun étant programmé pour répondre à un membre d'équipage différent. Pour induire l'équipage en erreur, chaque bouton est mal étiqueté au hasard avec le nom d'un autre membre de l'équipage. Chaque membre d'équipage est autorisé à appuyer sur jusqu'à quatre des boutons, dans n'importe quel ordre. Chaque fois qu'ils appuieront sur un bouton, ils verront à qui appartient réellement le bouton. Dans leurs quatre essais, ils doivent trouver le bouton qui leur est assigné. Pour que l'équipage soit libre, tous doivent réussir cette tâche. Si même l'un d'entre eux échoue, tous seront exécutés. Une fois qu'un membre d'équipage a terminé sa tentative, il doit être isolé sans aucun moyen de transmettre des informations à l'un de ses coéquipiers.

Les chances de succès semblent infimes. Si les membres de l'équipage choisissent des boutons au hasard, chacun aura 1 chance sur 2 de trouver son bouton. La chance que les huit réussissent n'est que de 1 sur 256, soit environ 0.4 %.

Mais ils n'ont pas à appuyer sur des boutons au hasard. Une façon d'augmenter la probabilité de succès pourrait être d'égaliser toutes les pressions sur les boutons d'une manière ou d'une autre. Cela nous amène à notre première question casse-tête.

Puzzle 1

De combien la probabilité de survie de l'équipage peut-elle être améliorée s'il s'assure que chaque bouton est appuyé aussi souvent (au lieu d'appuyer sur quatre boutons au hasard) ?

Rob Corlet et JPayette ont bien répondu à cette question, comme ils l'ont fait à toutes les autres questions. Quant à l'idée centrale insaisissable derrière les énigmes de cette colonne, Rob Corlett, JPayette et Jouni Seppänen le décrivait magnifiquement, tandis que Sacha Bugnon apporté une solution informatique.

Voici la réponse de Rob Corlett :

Une façon de s'assurer que chaque bouton est appuyé un nombre égal de fois est de séparer les prisonniers en deux groupes de taille égale de 4.

Chaque groupe n'appuie que sur les boutons correspondant aux membres de son groupe. Ainsi, si A, B, C et D sont tous dans le même sous-groupe, ils n'appuient que sur les boutons pour A, B, C et D.

Cela change le problème en demandant la probabilité que chaque prisonnier soit affecté au bon groupe, car il est alors garanti d'appuyer sur son bouton en quatre pressions ou moins.

Le nombre de façons de peupler le premier groupe (et donc le deuxième groupe également) avec quatre personnes est le nombre de façons de choisir 4 sur 8 soit C(8, 4) = 70. Par conséquent, le nombre total de façons de répartir tout le monde dans les deux groupes est de 70.

Il n'y a qu'une seule allocation qui attribue correctement chaque prisonnier au bon groupe et donc la probabilité que tout le monde soit dans le bon groupe et que tous les prisonniers survivent est de 1/70, ce qui est 3.66 fois mieux que le 1/256 de la stratégie précédente. [Mais c'est encore très petit : juste 1.4 % de chance.]

Puzzle 2

Il existe un moyen d'améliorer les cotes lamentables d'origine de plus de 90 fois, à environ 36.5 %, ce qui semble miraculeux ! Cette stratégie implique l'utilisation de boucles ou de chaînes de suppositions - d'où les références à la nébuleuse du collier et aux Catenati (chaîne est latin pour chaîne). Dans la forme de base de la stratégie, chaque membre d'équipage commence par appuyer sur le bouton portant son nom, puis passe au bouton portant le nom du membre d'équipage auquel appartenait réellement le premier bouton, et ainsi de suite, créant une chaîne de noms.

Voyons comment cela fonctionne en pratique. Dans le diagramme, les boutons sont affichés avec leurs étiquettes en blanc. Les lettres bleues ci-dessous indiquent les véritables propriétaires des boutons. Lorsque le premier membre d'équipage, A, entre dans la salle de la roulette, il appuie d'abord sur le bouton A. C'est le bouton de C, donc elle appuie ensuite sur le bouton C, puis sur le bouton E et enfin sur le bouton F, qui est en fait le propre bouton de A, donc elle l'a trouvé avec succès en quatre essais. Notez que les boutons ACEF forment une boucle fermée de quatre boutons. Lorsque les membres d'équipage C, E et F se relaient, ils parcourront également la même boucle fermée, en partant de leurs places respectives, et trouveront également leurs propres boutons en quatre essais.

Cet arrangement a également deux boucles plus petites de deux boutons chacune : BD et GH. Ces quatre membres d'équipage trouveront leurs propres boutons en deux essais. Ainsi, avec cet arrangement, tous les membres de l'équipage réussiront et ils auront mérité leur liberté. Il est clair que si l'arrangement ne contient que des boucles de longueur 4 ou moins, tous les membres d'équipage auront gain de cause et seront libérés. Si, d'autre part, il y a une seule boucle de 5 ou plus, alors tous les membres d'équipage sur cette boucle ne parviendront pas à trouver leur bouton en quatre essais, et l'équipage sera exécuté. Afin de trouver la probabilité de succès, nous pouvons trouver la probabilité d'avoir une boucle de 5, 6, 7 ou 8, les additionner et soustraire cette somme de 1. C'est plus facile à calculer que l'inverse car pour huit boutons, il ne peut y avoir qu'une seule boucle ayant 5, 6, 7 ou 8 membres.

Il y en a 8 ! différentes façons d'organiser huit boutons. Mais lorsque nous faisons des boucles, la même boucle représente huit de ces arrangements (ABCDEFGH forme la même boucle que BCDEFGHA, qui est la même que CDEFGHAB, etc.). Ainsi, la probabilité d'avoir une boucle de taille 8 est (8 !/8)/8 !, soit simplement 1/8. De même, la probabilité d'avoir une boucle de taille 7 est de 1/7, de taille 6 est de 1/6 et de taille 5 est de 1/5. Par conséquent, la probabilité de succès pour notre équipage intrépide est de 1 − (1/5 + 1/6 + 1/7 + 1/8), soit 36.5 %, comme mentionné précédemment.

La stratégie ci-dessus fonctionne pour n'importe quel nombre de prisonniers, et l'amélioration des chances par rapport à l'approche aléatoire augmente rapidement à mesure que ce nombre augmente. Il est environ septuple pour quatre détenus, 24 fois pour six, 93 fois pour huit et un étonnant (3.8 × 1029)-pli pour 100 prisonniers. La clé pour comprendre cette énorme augmentation est que la méthode lie le succès ou l'échec de chaque membre du groupe à celui des autres. Dans une très large mesure, ils réussissent ou échouent tous ensemble. La probabilité de succès du groupe ne baisse pas trop par rapport à celle d'une personne seule, passant seulement de 50 % pour un seul détenu à 30.69 % à mesure que le nombre de détenus augmente sans limite. D'un autre côté, la probabilité de réussite d'une approche aléatoire ou même d'une approche « même pression sur un bouton » diminue rapidement jusqu'à être très proche de zéro, même pour un petit nombre de détenus.

Si la logique derrière cette stratégie semble encore floue, voici une analyse du problème des 100 prisonniers dans ce excellente vidéo de Veritasium.

Puzzle 3

Ce puzzle concernait le lieutenant Uhura se souvenant d'un jeu d'enfance, qui était essentiellement le même puzzle, mais pour six personnes. Comme indice, j'ai suggéré de résoudre le problème pour quatre personnes. Maintenant que nous avons la formule, nous pouvons facilement calculer les probabilités.

Pour quatre personnes, la probabilité que la boucle la plus longue soit juste 2 ou 1 est : 1 − (1/3 + 1/4) soit 41.7 % avec un gain de sept fois par rapport au choix aléatoire.

Pour six personnes, la probabilité que la boucle la plus longue soit 3, 2 ou 1 est : 1 − (1/4 + 1/5 + 1/6) soit 38.3 % avec un gain de plus de 24 fois par rapport au choix aléatoire.

Puzzle 4

Alors que notre histoire continue, il s'avère que l'un des Catenati a pris une aversion particulière pour le Entreprise l'équipage et les surveille à distance. Il soupçonne qu'ils ont mis au point une stratégie efficace basée sur le diagramme d'Uhura. Il est déterminé à déjouer leur plan en se glissant dans la chambre et en changeant délibérément l'ordre des étiquettes des boutons avant le début de la roulette. Peut-il réussir à contrecarrer le plan ? Qu'est-ce que l'équipe de débarquement doit faire particulièrement attention à dissimuler ?

Très tôt dans la discussion stratégique de l'équipage, les yeux d'Uhura se rétrécirent soudainement. Elle a donné un signal à son équipage et elle a commencé à parler en nicholese, annonçant: "Toute autre discussion en nicholese, s'il vous plaît." Le nicholese était une nouvelle langue qu'Uhura avait inventée au début de sa carrière pour ce genre de situation, pour contourner l'utilisation de traducteurs universels. "Vous avez dû remarquer cette Catenati suspecte", a-t-elle poursuivi. « Il pourrait essayer de nous saboter, nous devons donc modifier notre plan. Voici ce que nous devons faire… »

Uhura a décrit le nouveau plan jusqu'à ce qu'elle soit convaincue que chaque membre de son équipage le savait parfaitement. Puis elle a réfléchi, avec un regard lointain dans les yeux: «J'ai nommé Nicholese d'après une actrice emblématique du XXe siècle. Je suis content d'avoir insisté pour que Starfleet en fasse un standard sur tous nos vaisseaux.

Elle se retourna vers l'équipage. « C'est tout, officiers. Vous savez ce qu'il faut faire!"

Nous ne savons pas exactement ce qu'Uhura a dit à son équipe. Mais JPayette et Rob Corlett ont eu une assez bonne idée. Voici à nouveau Rob Corlett :

Si le diabolique Catenati entend qu'ils utilisent cette stratégie, il peut changer les noms affichés à l'écran pour s'assurer qu'il y a un cycle plus long que 4.

Pour briser cela, les prisonniers doivent alors accepter un ordre secret qui randomise la séquence. Ils le font en disant quelque chose comme « si vous voyez le nom d'Uhura, alors allez sur le bouton marqué Chekov. Si vous voyez le nom de Chekov affiché, allez sur le bouton marqué Smith, etc.

De cette façon, la réorganisation par les Catenati n'a pas d'importance car elle ne fonctionne que si vous connaissez la manière dont l'équipage répondra aux noms sur les écrans. Ils doivent cependant garder toute réorganisation secrète, sinon elle peut à nouveau être brisée.

Comme nous l'avons vu, Uhura s'est assuré que le secret serait gardé en sécurité. Chaque membre de l'équipage avait juste besoin d'utiliser le même ordre secret et de s'assurer que le maléfique Catenati ne savait pas ce que c'était. En fait, le changement d'ordre par le diabolique Catenati a en fait augmenté la probabilité de réussite de l'équipage !

C'est ce qui s'est passé. Uhura fut le premier à être emmené dans la chambre de la roulette. Elle appuya sur trois boutons. Aucun n'était à elle. Doit-elle être triste ou contente ? Elle retint son souffle et appuya sur sa quatrième. Elle avait trouvé son vrai bouton !

Elle savait qu'ils allaient tous être sauvés.

Puzzle 5

De quelle limite le pourcentage maximum de réussite s'approche-t-il lorsque la taille de l'équipe de débarquement augmente indéfiniment ? Pouvez-vous expliquer pourquoi cette méthode est tellement plus efficace que d'appuyer sur un bouton au hasard ?

J Payette a écrit :

Tout ce qui précède se généralise directement à un équipage de 2n membres chacun autorisé à appuyer au maximum n boutons. De Puzzle 2, nous déduisons que leurs chances de succès sont

1 − (somme sur k jusqu'à XNUMX fois n + 1 et 2n sur 1 /k).

La somme peut être comparée à l'intégrale de 1/x sur l'intervalle [n2n], ce qui nous permet de prouver que comme n croît jusqu'à l'infini, la probabilité ci-dessus diminue pour converger vers un étonnant 1 − ln(2) ≈ 30.6 %. [En fait 30.69 % à deux décimales.]

Rob Corlett a ajouté :

Si vous ne connaissez pas l'intégration, vous pouvez obtenir rapidement une réponse approximative par calcul à l'aide d'un tableur. Je suis arrivé à 0.307 une fois n atteint environ 750, ce qui est précis à 3 décimales près.

Nous avons déjà expliqué ci-dessus pourquoi cette méthode fonctionne. Toutes les boucles de plus de 1 sont partagées par plusieurs membres d'équipage. Leurs succès et leurs échecs sont donc fortement corrélés. C'est une illustration du principe "Tous pour un, et un pour tous". Tout droit sorti du manuel de Starfleet !

Merci à tous nos contributeurs. JPayette et Rob Corlett ont tous deux soumis des réponses primées qui ont rendu cette colonne de solutions presque redondante. Hélas, je dois m'en tenir à notre règle de choisir un gagnant par colonne de puzzle. Le prix Insights revient à JPayette en reconnaissance des contributions ici et dans le puzzle précédent. Toutes nos félicitations! Rob Corlett, vos contributions ne seront pas oubliées.

Rendez-vous le mois prochain pour de nouvelles Insights !

spot_img

Dernières informations

spot_img