Unsere Rätselaufgabe Letzten Monat war eine zu retten Star Trek Oberflächenpartei von acht, angeführt von der Unternehmen Kommunikationsoffizier Leutnant Uhura (gespielt vom späten Nichelle Nichols). Die Crew wird von einer außerirdischen Rasse, den Catenati, auf einem Planeten in den USA gefangen gehalten Halskette Nebel. Um zu entkommen, müssen sie ihre Wahrscheinlichkeit maximieren, eine Aufgabe zu erledigen, die zunächst nur eine düstere Erfolgswahrscheinlichkeit zu bieten scheint.
Die achtköpfige Besatzung wird über die Aufgabe informiert, während sie vorübergehend in einem Gemeinschaftsraum festgehalten wird, wo sie frei kommunizieren und Strategien entwickeln kann. In ein paar Stunden werden sie einzeln in einen Raum namens Roulette-Kammer geführt. Dieser Raum hat acht in einer Reihe angeordnete Tasten, von denen jede so programmiert ist, dass sie auf ein anderes Besatzungsmitglied reagiert. Um die Crew in die Irre zu führen, ist jeder Knopf willkürlich mit dem Namen eines anderen Crewmitglieds falsch beschriftet. Jedes Besatzungsmitglied darf bis zu vier der Knöpfe in beliebiger Reihenfolge drücken. Immer wenn sie einen Knopf drücken, sehen sie, wem der Knopf wirklich gehört. Innerhalb ihrer vier Versuche müssen sie den ihnen zugewiesenen Knopf finden. Damit die Besatzung freikommt, müssen alle diese Aufgabe meistern. Wenn auch nur einer von ihnen fehlschlägt, werden alle ausgeführt. Nachdem ein Besatzungsmitglied seinen Versuch beendet hat, muss es isoliert werden, ohne dass es möglich ist, Informationen an einen seiner Besatzungsmitglieder weiterzugeben.
Die Erfolgsaussichten scheinen winzig. Wenn Besatzungsmitglieder zufällig Knöpfe auswählen, hat jeder eine Chance von 1 zu 2, seinen Knopf zu finden. Die Chance, dass alle acht erfolgreich sind, beträgt nur 1 zu 256 oder etwa 0.4 %.
Aber sie müssen nicht wahllos Knöpfe drücken. Eine Möglichkeit, die Erfolgswahrscheinlichkeit zu erhöhen, könnte darin bestehen, alle Tastendrücke auf irgendeine Weise auszugleichen. Das bringt uns zu unserer ersten Rätselfrage.
Puzzle 1
Um wie viel kann die Überlebenswahrscheinlichkeit der Besatzung verbessert werden, wenn sie darauf achtet, dass jeder Knopf gleich oft gedrückt wird (anstatt vier beliebige Knöpfe zufällig zu drücken)?
Rob Corlett und JPayette beantworteten diese gut, wie sie auch alle anderen Fragen taten. Was die schwer fassbare zentrale Idee hinter den Rätseln in dieser Kolumne betrifft, so sind Rob Corlett, JPayette und Jouni Seppänen beschrieb es schön, während Sacha Bugon steuerte eine Computerlösung bei.
Hier ist die Antwort von Rob Corlett:
Eine Möglichkeit, sicherzustellen, dass jeder Knopf gleich oft gedrückt wird, besteht darin, die Gefangenen in zwei gleich große Gruppen von 4 Personen zu teilen.
Jede Gruppe drückt nur die Schaltflächen, die den Mitgliedern ihrer Gruppe entsprechen. Wenn also A, B, C und D alle in derselben Untergruppe sind, drücken sie nur die Tasten für A, B, C und D.
Dies verändert das Problem dahingehend, dass nach der Wahrscheinlichkeit gefragt wird, dass jeder Gefangene der richtigen Gruppe zugeordnet wird, da er dann garantiert seinen Knopf in vier oder weniger Drücken drückt.
Die Anzahl der Möglichkeiten, die erste Gruppe (und damit auch die zweite Gruppe) mit vier Personen zu besetzen, ist die Anzahl der Möglichkeiten, 4 aus 8 auszuwählen, was C(8, 4) = 70 ist. Daher die Gesamtzahl der Möglichkeiten von Die Zuteilung aller in die beiden Gruppen beträgt 70.
Es gibt nur eine Zuordnung, die jeden Gefangenen korrekt der richtigen Gruppe zuordnet, und so beträgt die Wahrscheinlichkeit, dass alle in der richtigen Gruppe sind und alle Gefangenen überleben, 1/70, was 3.66-mal besser ist als 1/256 der vorherigen Strategie. [Aber es ist immer noch sehr klein: nur eine Wahrscheinlichkeit von 1.4 %.]
Puzzle 2
Es gibt eine Möglichkeit, die ursprünglichen düsteren Chancen um das 90-fache auf etwa 36.5 % zu verbessern, was wie ein Wunder erscheint! Diese Strategie beinhaltet die Verwendung von Schleifen oder Ketten von Vermutungen – daher die Verweise auf den Halskettennebel und die Catenati (Kette ist lateinisch für Kette). In der Grundform der Strategie drückt jedes Besatzungsmitglied zunächst den Knopf mit seinem Namen, fährt dann mit dem Knopf fort, der den Namen des Besatzungsmitglieds trägt, dem der erste Knopf tatsächlich gehörte, und so weiter, wodurch eine Namenskette entsteht.
Mal sehen, wie das in der Praxis funktioniert. In der Abbildung sind die Schaltflächen mit ihrer Beschriftung weiß dargestellt. Die blauen Buchstaben unten zeigen die wahren Besitzer der Schaltflächen. Wenn das erste Besatzungsmitglied, A, die Roulettekammer betritt, drückt sie zuerst den Knopf A. Dies ist der Knopf von C, also drückt sie als nächstes Knopf C, dann Knopf E und schließlich Knopf F, der tatsächlich der Knopf von A ist, also hat sie ihn in vier Versuchen erfolgreich gefunden. Beachten Sie, dass die Schaltflächen ACEF eine geschlossene Schleife aus vier Schaltflächen bilden. Wenn die Besatzungsmitglieder C, E und F an der Reihe sind, werden sie ebenfalls dieselbe geschlossene Schleife durchlaufen, beginnend an ihren eigenen jeweiligen Plätzen, und auch ihre eigenen Knöpfe in vier Versuchen finden.
Diese Anordnung hat auch zwei kleinere Schleifen mit jeweils zwei Knöpfen: BD und GH. Diese vier Besatzungsmitglieder werden ihre eigenen Knöpfe innerhalb von zwei Versuchen finden. Mit dieser Anordnung werden also alle Besatzungsmitglieder erfolgreich sein und sich ihre Freiheit verdient haben. Es ist klar, dass, wenn das Arrangement nur Loops der Länge 4 oder weniger enthält, alle Besatzungsmitglieder erfolgreich sein und befreit werden. Wenn es andererseits eine einzelne Schleife von 5 oder mehr gibt, werden alle Besatzungsmitglieder in dieser Schleife ihren Knopf in vier Versuchen nicht finden, und die Besatzung wird hingerichtet. Um die Erfolgswahrscheinlichkeit zu finden, können wir die Wahrscheinlichkeit einer Schleife von 5, 6, 7 oder 8 finden, sie addieren und diese Summe von 1 subtrahieren. Dies ist einfacher zu berechnen als umgekehrt, weil für acht Schaltflächen kann es nur eine einzige Schleife mit 5, 6, 7 oder 8 Mitgliedern geben.
Es gibt 8! verschiedene Möglichkeiten, acht Tasten anzuordnen. Aber wenn wir Schleifen machen, macht die gleiche Schleife acht dieser Anordnungen aus (ABCDEFGH bildet die gleiche Schleife wie BCDEFGHA, die die gleiche ist wie CDEFGHAB usw.). Die Wahrscheinlichkeit, eine Schleife der Größe 8 zu haben, ist also (8!/8)/8!, was einfach 1/8 ist. In ähnlicher Weise beträgt die Wahrscheinlichkeit für eine Schleife der Größe 7 1/7, für die Größe 6 1/6 und für die Größe 5 1/5. Daher beträgt die Erfolgswahrscheinlichkeit für unsere unerschrockene Crew 1 − (1/5 + 1/6 + 1/7 + 1/8) oder 36.5 %, wie bereits erwähnt.
Die obige Strategie funktioniert für eine beliebige Anzahl von Gefangenen, und die Verbesserung der Chancen gegenüber dem zufälligen Ansatz nimmt mit zunehmender Anzahl schnell zu. Es ist ungefähr das Siebenfache für vier Gefangene, das 24-fache für sechs, das 93-fache für acht und eine erstaunliche (3.8 × 1029)-fach für 100 Gefangene. Der Schlüssel zum Verständnis dieses enormen Anstiegs liegt darin, dass die Methode den Erfolg oder Misserfolg jedes Mitglieds der Gruppe mit dem der anderen verknüpft. Weitgehend erfolgreich oder scheitern sie alle gemeinsam. Die Erfolgswahrscheinlichkeit der Gruppe sinkt nicht allzu sehr von der einer einzelnen Person ab, sondern sinkt nur von 50 % für einen einzelnen Gefangenen auf 30.69 %, wenn die Anzahl der Gefangenen unbegrenzt erhöht wird. Andererseits sinkt die Wahrscheinlichkeit, dass eine zufällige Annäherung oder sogar eine „gerade Knopfdrücke“-Annäherung erfolgreich ist, selbst für eine kleine Anzahl von Gefangenen schnell auf sehr nahe Null.
Wenn die Logik hinter dieser Strategie immer noch verschwommen erscheint, hier ist eine Analyse des 100-Gefangenen-Problems darin ausgezeichnetes Video von Veritasium.
Puzzle 3
Bei diesem Puzzle ging es um Lieutenant Uhura, der sich an ein Spiel aus seiner Kindheit erinnerte, das im Wesentlichen das gleiche Puzzle war, aber für sechs Personen. Als Hinweis schlug ich vor, das Problem für vier Personen zu lösen. Jetzt, da wir die Formel haben, können wir die Wahrscheinlichkeiten leicht berechnen.
Für vier Personen beträgt die Wahrscheinlichkeit, dass die längste Schleife nur 2 oder 1 ist: 1 − (1/3 + 1/4) oder 41.7 % mit einem siebenfachen Gewinn gegenüber einer zufälligen Auswahl.
Für sechs Personen beträgt die Wahrscheinlichkeit, dass die längste Schleife 3, 2 oder 1 ist: 1 − (1/4 + 1/5 + 1/6) oder 38.3 % mit mehr als einem 24-fachen Gewinn gegenüber einer zufälligen Auswahl.
Puzzle 4
Im weiteren Verlauf unserer Geschichte stellt sich heraus, dass einer der Catenati eine besondere Abneigung gegen die entwickelt hat Unternehmen Besatzung und überwacht sie aus der Ferne. Er vermutet, dass sie auf der Grundlage von Uhuras Diagramm eine effektive Strategie entwickelt haben. Er ist entschlossen, ihren Plan zu vereiteln, indem er in die Kammer schlüpft und absichtlich die Reihenfolge der Tastenbeschriftungen ändert, bevor das Roulette beginnt. Kann er den Plan erfolgreich durchkreuzen? Was muss der Landetrupp besonders sorgfältig verbergen?
Sehr früh in der Strategiediskussion der Crew verengten sich Uhuras Augen plötzlich. Sie gab ihrer Crew ein Zeichen, wechselte zu Nicholesisch und verkündete: „Alle weiteren Diskussionen bitte auf Nicholesisch.“ Nicholesisch war eine neue Sprache, die Uhura zu Beginn ihrer Karriere für genau solche Situationen erfunden hatte, um den Einsatz von Universalübersetzern zu umgehen. „Sie müssen diesen misstrauischen Catenati bemerkt haben“, fuhr sie fort. „Er könnte versuchen, uns zu sabotieren, also müssen wir unseren Plan ändern. Hier ist, was wir tun müssen … “
Uhura skizzierte den neuen Plan, bis sie überzeugt war, dass jedes Mitglied ihrer Crew ihn genau kannte. Dann überlegte sie mit einem abwesenden Blick in ihren Augen: „Ich habe Nicholese nach einer ikonischen Schauspielerin des 20. Jahrhunderts benannt. Ich bin froh, dass ich darauf bestanden habe, dass die Sternenflotte es auf allen unseren Schiffen zum Standard macht.“
Sie wandte sich wieder der Crew zu. „Das ist alles, Offiziere. Du weißt was zu tun ist!"
Wir wissen nicht genau, was Uhura ihrem Team gesagt hat. Aber JPayette und Rob Corlett hatten eine ziemlich gute Idee. Hier ist nochmal Rob Corlett:
Wenn der böse Catenati hört, dass er diese Strategie anwendet, kann er die auf dem Display angezeigten Namen ändern, um sicherzustellen, dass es einen Zyklus gibt, der länger als 4 ist.
Um dies zu brechen, müssen die Gefangenen einer geheimen Anordnung zustimmen, die die Reihenfolge zufällig bestimmt. Sie tun dies, indem sie etwas sagen wie: „Wenn Sie Uhuras Namen sehen, dann gehen Sie zu der Schaltfläche mit der Aufschrift Chekov. Wenn Sie sehen, dass Chekovs Name angezeigt wird, gehen Sie zu der Schaltfläche, die mit Smith gekennzeichnet ist, usw.“
Auf diese Weise spielt die Neuordnung durch die Catenati keine Rolle, da dies nur funktioniert, wenn Sie wissen, wie die Besatzung auf die Namen auf den Displays reagiert. Sie müssen jedoch jede Neuordnung geheim halten, sonst kann es wieder gebrochen werden.
Wie wir gesehen haben, hat Uhura dafür gesorgt, dass das Geheimnis gewahrt bleibt. Jedes Mitglied der Crew musste nur die gleiche geheime Reihenfolge verwenden und sicherstellen, dass der böse Catenati nicht wusste, was es war. Tatsächlich erhöhte die geänderte Reihenfolge der bösen Catenati die Erfolgswahrscheinlichkeit der Crew!
Das ist, was passiert ist. Uhura war die erste, die in die Roulettekammer gebracht wurde. Sie drückte drei Knöpfe. Keine gehörte ihr. Soll sie traurig oder froh sein? Sie hielt den Atem an und drückte ihre vierte. Sie hatte ihren wahren Knopf gefunden!
Sie wusste, dass sie alle gerettet werden würden.
Puzzle 5
Welcher Grenze nähert sich der maximale Prozentsatz des Erfolgs, wenn die Größe der Landegruppe unbegrenzt zunimmt? Können Sie erklären, warum diese Methode so viel effizienter ist als das zufällige Drücken von Tasten?
JPayette schrieb:
Alle oben genannten Punkte lassen sich direkt auf eine 2-köpfige Besatzung übertragenn Mitglieder dürfen jeweils höchstens drücken n Tasten. Aus Rätsel 2 leiten wir ab, dass ihre Erfolgsaussichten bestehen
1 − (summieren k zwischen n + 1 und 2n von 1 /k).
Die Summe ist vergleichbar mit dem Integral von 1/x über das Intervall [n, 2n], was uns erlaubt, das zu beweisen als n gegen unendlich wächst, nimmt die obige Wahrscheinlichkeit ab und konvergiert gegen erstaunliche 1 − ln(2) ≈ 30.6 %. [Eigentlich 30.69 % auf zwei Dezimalstellen.]
Rob Corlett fügte hinzu:
Wenn Sie die Integration nicht kennen, können Sie durch Berechnung mit einer Tabellenkalkulation schnell zu einer ungefähren Antwort kommen. Ich bin einmal auf 0.307 gekommen n erreichte ungefähr 750, was auf 3 Dezimalstellen genau ist.
Warum diese Methode funktioniert, haben wir oben bereits erklärt. Alle Schleifen, die länger als 1 sind, werden von mehreren Besatzungsmitgliedern geteilt. Ihre Erfolge und Misserfolge sind also stark korreliert. Es ist eine Veranschaulichung des Prinzips „Alle für einen, einer für alle“. Direkt aus dem Handbuch der Sternenflotte!
Vielen Dank an alle unsere Mitwirkenden. JPayette und Rob Corlett lieferten beide preiswürdige Antworten, die diese Lösungskolumne fast überflüssig erscheinen ließen. Leider muss ich mich an unsere Regel halten, einen Gewinner pro Rätselspalte auszuwählen. Der Insights-Preis geht an JPayette als Anerkennung für Beiträge hier und im vorherigen Puzzle. Herzliche Glückwünsche! Rob Corlett, Ihre Beiträge werden unvergessen bleiben.
Bis nächsten Monat für neue Insights!
