100 (oder einige gerade 2N :-)) Gefangene sind in einem Raum A. Sie sind von 1 bis 100 nummeriert.
Einer nach dem anderen (von Häftling Nr. 1 bis Häftling Nr. 100, in Ordnung) werden sie in einen Raum B gelassen, in dem 100 Kisten (von 1 bis 100 nummeriert) auf sie warten. Innerhalb der (geschlossenen) Boxen sind Zahlen von 1 bis 100 (die Zahlen in den Boxen sind zufällig permutiert!).
Sobald er in Raum B ist, kann jeder Gefangene 50 Kartons öffnen (er wählt, welche er öffnet). Wenn er die Nummer findet, die ihm in einer dieser 50 Boxen zugewiesen wurde, kommt der Gefangene in einen Raum C und alle Boxen werden wieder geschlossen, bevor der nächste in Raum B aus Raum A kommt Zimmer A, B und C) wird getötet.
Vor dem Betreten von Raum B können sich die Gefangenen auf eine Strategie (Algorithmus) einigen. Es gibt keine Möglichkeit, zwischen Räumen zu kommunizieren (und in Raum B kann keine Nachricht hinterlassen werden!).
Gibt es einen Algorithmus, der die Wahrscheinlichkeit maximiert, dass alle Gefangenen überleben? Welche Wahrscheinlichkeit erreicht dieser Algorithmus?
Anmerkungen:
Nach dem Zufallsprinzip (was Sie "keine Strategie" nennen) gibt es zwar für jeden Gefangenen eine Wahrscheinlichkeit von 1/2, aber dann ist die Wahrscheinlichkeit, dass alle überleben, 1/2 ^ 100 (was ziemlich niedrig ist) ). Man kann viel besser machen!
Die Gefangenen dürfen die Boxen nicht neu ordnen!
Alle Gefangenen werden getötet, wenn ein Gefangener seine Nummer zum ersten Mal nicht findet. Und ist keine Kommunikation möglich.
Hinweis : Im Durchschnitt kann man mehr als 30 Gefangene retten , was viel mehr ist als (50/100) * (50/99) * [ ...] * 1
Ich finde eine Low-Tech-Lösung für diese Art von Problem ist immer der beste Weg zu gehen.
Zuerst machen wir einige Annahmen über die Situation
Mit einer Wahrscheinlichkeit von 0,005%, dass sie morgen sehen werden, gibt es eine sehr einfache und wenig technische Lösung für dieses Problem. RIOT
Alles dreht sich um Verluste und potentielle Gewinne, die Chancen, dass die Gefangenen weit außerhalb der Wachen sind und sich gegenseitig als menschliche Schilde benutzen, da sie sowieso alle tot sind, wenn sie es nicht tun, können sie die Chancen erhöhen Übermacht einen Wächter, sobald sie seine Waffe dort haben, steigt die Chance auf und hilft ihnen über die Macht mehr Wachen, um mehr Feuerkraft zu erhalten, um ihre Überlebensrate weiter zu erhöhen. Sobald die Wärter wissen, was passiert, werden sie wahrscheinlich nach den Hügeln rennen und das Gefängnis absperren, dies wird den Medien einen Kopf geben und dann ist es eine Menschenrechtsfrage.
Implementieren Sie einen Sortieralgorithmus und sortieren Sie die Boxen nach den darin enthaltenen Zahlen.
Der erste Häftling sortiert 50 Kisten, der zweite Häftling sortiert die anderen 50 Kisten und verschmilzt mit der ersten. (Beachten Sie, dass der zweite Häftling die Werte innerhalb der ersten 50 Felder erraten kann)
Nach dem zweiten Häftling werden alle Kisten sortiert sein !!!
Alle anderen können die Kästchen mit ihren Nummern leicht öffnen.
Ich weiß nicht, ob das erlaubt ist, aber die beste Annäherung, die ich finden kann, ist:
EDIT: Ok, ich denke, das macht es. Natürlich behandle ich das als ein Computerproblem, ich glaube nicht, dass ein Prisoner das ausführen kann, obwohl es ziemlich einfach ist, wenn Sie es nicht tun.
Finde die ersten 50 Primzahlen, lass uns annehmen, dass wir sie in einem Array namens primes halten.
Wiederholen. Nach dem ersten Prisoner wäre die Gesamtzeit für ihn: 3 ^ m * 5 ^ n * 7 ^ p ... = X
Bevor der zweite Prisor den Raum betritt, faktorisiert X. Sie kennen vorher die Primzahlen, die verwendet wurden, so dass die Faktorisierung trivial ist. Auf diese Weise erhalten Sie m, n, p usw., so dass der zweite Prisoner jede Box- / Zahlenkombination kennt, die der vorherige Prisoner verwendet hat.
Die Wahrscheinlichkeit, dass die erste Person alle tötet, ist 1/2, die zweite hat eine 50 / (100 - n) (die Anzahl der Versuche der ersten), die dritte wird 50 / ( 100 - n - m) (wenn n + m = 100 dann sind alle Positionen bekannt) und so weiter.
Offensichtlich muss der nächste Priser die bereits bekannten Boxen überspringen (mit Ausnahme der letzten Wahl, wenn die Box, die seine Nummer enthält, bereits bekannt ist)
Ich weiß nicht, was genau die Möglichkeit ist, da es davon abhängt, wie viele Entscheidungen sie treffen müssen, aber ich würde sagen, es ist ziemlich hoch.
EDIT: Wenn der Prissioner nicht aufhören muss, wenn er seine Nummer erreicht hat, dann ist die Wahrscheinlichkeit für die ganze Gruppe um genau 50% verbessert.
EDIT2: @OysterD sieht es so. Wenn der erste Prisor 50 Boxen öffnen kann, weiß der zweite, ob seine Nummer in einem dieser Boxen ist. Wenn dies der Fall ist, kann er andere 49 öffnen (und dadurch die Box- / Zahlenkombination der 100 Boxen lernen) und schließlich seine eine öffnen. Wenn also der erste Prifer erfolgreich war, dann hat jeder Erfolg. Denken Sie daran, dass jeder Prisor eine Möglichkeit für den anderen bietet, genau die Boxen / Zahlenkombination für jede Box zu kennen, die er öffnet.
Vielleicht lese ich es nicht richtig, aber die Frage scheint schlecht aufgebaut zu sein oder fehlende Informationen zu enthalten.
Wenn er die Nummer findet, die war ihm in einem dieser 50 zugeordnet Kisten, in die der Häftling hineinläuft ein Zimmer C und alle Boxen sind geschlossen wieder bevor der nächste reinkommt Zimmer B von Zimmer A. Ansonsten alle Gefangene (in den Räumen A, B und C) bekommen getötet.
Bedeutet der letzte Satz, dass alle Gefangenen getötet werden, wenn ein Häftling zum ersten Mal seine Nummer nicht findet? Wenn nicht, was passiert mit Gefangenen, die ihre Nummer nicht finden?
Wenn keine Kommunikation möglich ist und immer wenn ein Gefangener den Raum B betritt, ist er immer in einem identischen Zustand, dann gibt es keine Möglichkeit für eine Strategie.
Die Gefangenen könnten sagen, bevor sie Zimmer A verlassen, welche Nummernbox sie öffnen werden. Aber ohne nachfolgende Gefangene, die wissen, ob sie erfolgreich waren oder nicht (vorausgesetzt, dass das Scheitern nicht für alle fehlschlägt), wenn der nächste Gefangene den Raum B betritt, haben sie immer noch die gleiche Chance, ihre Nummer zu wählen (immer 1: 100) .
Wenn das Scheitern für alle ein Fehlschlag für alle ist, dann könnte jeder nachfolgende Gefangene, wenn er weiß, welche Kiste die früheren Gefangenen geöffnet haben, und aufgrund der Tatsache, dass sie nicht alle getötet wurden, die Wahrscheinlichkeit verringern, die falsche Kiste zu wählen eine Schachtel. d. h. 1: 100 für den ersten Gefangenen, 1:99 für den zweiten, bis zum 1: 1 für den letzten.
Die Gefangenen könnten zustimmen, dass Häftling 1 die Kästchen 1-50 öffnet.
Wenn sie alle noch am Leben sind, stimmen sie zu, dass der nächste Gefangene die Felder 2-51 öffnet. (Die 2 ist willkürlich, aber man kann sich leicht an diese Regel erinnern) Seine Überlebenschancen , da P1 überlebt hat sind jetzt 50/99. Sie möchten das Öffnen einer Box verhindern, wenn Sie wissen, dass der vorherige Typ seine gefunden hat.
Ich weiß nicht, ob das optimal ist, aber es ist viel besser als zufällig.
Die Überlebenswahrscheinlichkeit, die aussieht wie
50/100 * 50/99 * 50/98 *. . .50 / 51 * 1
Ich denke, da keine Kommunikation möglich ist, würde die beste Strategie beinhalten
Verteilung der Wahrscheinlichkeit von jedem Gefangenen so gleichmäßig wie möglich
Bin ich auf dem richtigen Weg oder nicht?
Informationen für jeden Gefangenen:
- Die Anzahl der überlebten Gefangenen. Wenn Sie also ein effizientes Box-Picking-System haben, das den Befehl nutzt, dass ein Gefangener den Raum B betritt, dann ist definitiv eine Strategie möglich
- Welche Kästen haben die früheren Gefangenen ausgewählt? Natürlich ist während des Laufs keine Kommunikation möglich und es wäre nicht möglich, sich an irgendeine 100er Box-Auswahl-Permutation zu erinnern. Sie können diese Informationen jedoch dazu verwenden, in einem System zu berechnen, bevor der Lauf beginnt.
Meine Meinung:
- Zeichnen Sie eine Tabelle mit Zahlen mit 2 Spalten, die erste Spalte enthält die Boxnummer (von Box 1 bis Box 100). Jeder Gefangene muss dann 50 Boxen und jede Box, die er wählt, auswählen und 1 Markierung auf die entsprechende Reihe in der zweiten Spalte setzen.
- Alle Gefangenen sind jedoch verpflichtet, niemals zweimal eine Kiste zu wählen. Und keine Box darf mit mehr als 50 markiert werden. Manche Häftlinge bekommen vielleicht weniger Optionen als andere, da manche Kisten erst zu 50 Mark gefüllt werden können.
- Wenn ein Gefangener in Raum B gebracht wird, öffnet er / sie alle Kästchen, die er markiert hat.
Gleiches Konzept.
Nehmen Sie an:
- Schreiben Sie eine Liste der ersten 100 Binärzahlen auf, die fünfzig 1s und fünfzig 0s hat.
- Sortiere sie vom niedrigsten zum höchsten.
- Gefangener # 1 bekommt die erste Nummer, Gefangener # 2 bekommt den zweiten, Gefangener # 3 bekommt den dritten und so weiter ...
- Jeder Gefangene erinnert sich an seine / ihre Binärzahl.
- Wenn ein Gefangener in Raum B gebracht wird, passt er / sie die Binärziffern der Nummer an, die er in jedem der Kästchen gespeichert hat, das höchste Bit wird mit der linken Box abgeglichen, das nächsthöchste Bit wird mit dem zweiten verglichen linkes Feld ... das niedrigste Bit wird mit dem Feld ganz rechts abgeglichen.
- Er / sie öffnet alle mit 1 übereinstimmenden Kästchen und lässt geschlossene Kästchen mit 0 übereinstimmen.
Dies würde die Wahrscheinlichkeit verringern, weil frühe Häftlinge Ziffern bekommen, die sich von den späteren Häftlingen unterscheiden, und Häftlinge, deren Zahl nahe beieinander liegt, würden Ziffern nahe beieinander bekommen. Dies garantiert zwar nicht die Überlebensfähigkeit, aber wenn die frühen Häftlinge überleben, besteht die Chance, dass die späteren Häftlinge auch eine höhere Überlebenswahrscheinlichkeit haben.
Ich habe jedoch nicht die genauen Zahlen und Gründe durchdacht, aber dies ist eine schnelle Lösung, die ich mir im Moment vorstellen kann.
Es gibt keine Zeitlimits in der Frage, daher schlage ich vor, dass Gefangene sich entschließen sollten, 1 Stunde pro Kasten zu nehmen und sie in der angegebenen Reihenfolge zu öffnen. Wenn der zweite Gefangene nach 2 Stunden in den Raum gelassen wird, weiß er, dass der erste Häftling in Feld 2 seine eigene Nummer gefunden hat. Deshalb kann er in seiner Sequenz Box 2 überspringen und die Kästchen 1, 3, 4 ... 51 öffnen Die Verlusten der ersten Gefangenen liegen bei 50/100 Geben Sie, dass der erste Häftling überlebte, dann ist die zweite Häftlingswahrscheinlichkeit 50/99 Die Antwort scheint also ((50 ^ 51) * 49!) / 100 zu sein! was laut Google 2,89 * 10 ^ -9 macht Das ist ziemlich Null Selbst wenn die Häftlinge die Kisten wüssten, auf denen die Glücklichen ihre Nummer gefunden hatten, gab es keine Hoffnung.