Finden Sie Ihre eigene Nummer in einem Feld

https://stackoverflow.com/questions/34345

09-06-2019
|

Frage

100 (oder einige sogar 2N :-) ) Gefangene sind in einem Raum A.Sie sind von 1 bis 100 nummeriert.

Einer nach dem anderen (in der Reihenfolge von Häftling Nr. 1 bis Häftling Nr. 100) werden sie in einen Raum B gelassen, in dem 100 Kisten (nummeriert von 1 bis 100) auf sie warten.In den (geschlossenen) Kästchen befinden sich Zahlen von 1 bis 100 (die Zahlen in den Kästchen sind zufällig permutiert!).

Im Raum B darf jeder Gefangene 50 Kisten öffnen (er entscheidet, welche er öffnet).Findet er in einer dieser 50 Kisten die ihm zugewiesene Nummer, darf der Gefangene einen Raum C betreten und alle Kisten werden wieder verschlossen, bevor der nächste aus Raum A in Raum B geht.Andernfalls werden alle Gefangenen (in den Räumen A, B und C) getötet.

Vor dem Betreten von Raum B können sich die Gefangenen auf eine Strategie (Algorithmus) einigen.Es gibt keine Möglichkeit, zwischen den Räumen zu kommunizieren (und in Raum B kann keine Nachricht hinterlassen werden!).

Gibt es einen Algorithmus, der die Überlebenswahrscheinlichkeit aller Gefangenen maximiert?Welche Wahrscheinlichkeit erreicht dieser Algorithmus?

Anmerkungen:

Dinge nach dem Zufallsprinzip zu tun (was Sie „keine Strategie“ nennen) ergibt zwar eine Wahrscheinlichkeit von 1/2 für jeden Gefangenen, aber dann beträgt die Wahrscheinlichkeit, dass alle überleben, 1/2^100 (was ziemlich niedrig ist).Man kann es viel besser machen!
Den Gefangenen ist es nicht gestattet, die Kisten nachzubestellen!
Alle Gefangenen werden getötet, wenn ein Gefangener zum ersten Mal seine Nummer nicht findet. Und Es ist keine Kommunikation möglich.
Hinweis:man kann mehr als 30 Gefangene retten im Durchschnitt, was viel mehr ist als (50/100) * (50/99) * [...] * 1

Lösung

Dieses Rätsel wird unter erklärt http://www.math.princeton.edu/~wwong/blog/blog200608191813.shtml und diese Person kann das Problem viel besser erklären.

Die Aussage „Alle Gefangenen werden getötet“ ist falsch.Auch das „im Schnitt kann man 30+ sparen“ sei falsch, das Artikel sagt, dass man in 30 % der Fälle 100 % der Gefangenen retten kann.

Andere Tipps

Ich finde, dass eine Low-Tech-Lösung für diese Art von Problem immer der beste Weg ist.

Zuerst machen wir einige Annahmen über die Situation

Die Gefangenen sind nicht alle Programmierer oder Mathematiker
Sie wollen nicht sterben
Die Wachen sind gut bewaffnet

Mit einer Wahrscheinlichkeit von 0,005 %, dass sie es morgen sehen, gibt es eine sehr einfache und technologiearme Lösung für dieses Problem. AUFSTAND

Es geht um Verluste und potenzielle Gewinne. Die Wahrscheinlichkeit ist groß, dass die Gefangenen den Wärtern zahlenmäßig weit überlegen sind, und wenn sie sich gegenseitig als menschliche Schutzschilde benutzen, da sie sowieso alle tote Männer sind, können sie, wenn sie es nicht tun, ihre Chancen erhöhen, die Macht zu übernehmen Wache, sobald sie seine Waffe haben, steigt ihre Chance, was ihnen hilft, mehr Wachen zu überwältigen, um mehr Feuerkraft zu erhalten und ihre Überlebensrate weiter zu erhöhen.Sobald die Wärter merken, was passiert, werden sie wahrscheinlich in die Berge rennen und das Gefängnis absperren. Das wird die Medien informieren und dann ist es eine Menschenrechtsfrage.

Implementieren Sie einen Sortieralgorithmus und sortieren Sie die Kästchen nach den darin enthaltenen Zahlen.

Der erste Gefangene sortiert 50 Kisten, und der zweite Gefangene sortiert die anderen 50 und bringt sie mit dem ersten zusammen.(Beachten Sie, dass der zweite Gefangene die Werte in den ersten 50 Kästchen erraten kann.)

Nach dem 2. Gefangenen werden alle Kisten in einer sortierten Reihenfolge sein !!!

Alle anderen können dann die Boxen mit ihren Nummern ganz einfach öffnen.

Ich weiß nicht, ob das erlaubt ist, aber die beste Annäherung, die ich finden kann, ist:

BEARBEITEN:Ok, ich denke, das reicht aus.Natürlich betrachte ich das als ein Computerproblem. Ich glaube nicht, dass irgendein Gefangener dazu in der Lage sein wird, obwohl es ziemlich einfach ist, wenn man es nicht tut.

Finden Sie die ersten 50 Primzahlen. Nehmen wir an, wir speichern sie in einem Array namens Primzahlen.

Der erste Gefangene betritt Raum B, öffnet die erste Kiste und findet die Nummer m.
Wait primes[1]^m (das wäre 3^m)
Öffnen Sie Box 2 und lesen Sie die Nummer ab --> n
Warten Sie (primes[2]^n - 1) * primes[1]^m, das wäre (5^n - 1) * 3^m und die Gesamtzeit, die er gewartet hat, wäre 3^n * 5^n

Wiederholen.Nach dem ersten Gefangenen wäre die Gesamtzeit für ihn:3^m * 5^n * 7^p ...= X

Faktorisieren Sie X, bevor der zweite Gefangene den Raum betritt.Da Sie die verwendeten Primzahlen im Voraus kennen, ist die Faktorisierung trivial.Auf diese Weise erhalten Sie m, n, p usw., sodass der zweite Gefangene jede Kästchen-/Zahlenkombination kennt, die der vorherige Gefangene verwendet hat.

Die Wahrscheinlichkeit, dass der erste alle tötet, beträgt 1/2, der zweite hat 50 / (100 - n) (wobei n die Anzahl der Versuche des ersten ist), der dritte hat 50 / (100 - n). - m) (wenn n + m = 100, dann sind alle Positionen bekannt) und so weiter.

Offensichtlich muss der nächste Gefangene die bereits bekannten Kästchen überspringen (mit Ausnahme der letzten Auswahl, wenn das Kästchen, das seine Nummer enthält, bereits bekannt ist).

Ich weiß nicht, wie hoch die genaue Wahrscheinlichkeit ist, da sie davon abhängt, wie viele Entscheidungen sie treffen müssen, aber ich würde sagen, dass sie ziemlich hoch ist.

BEARBEITEN:Wenn der Gefangene nicht aufhören muss, wenn er seine Nummer erhält, erhöht sich die Wahrscheinlichkeit für die gesamte Gruppe erheblich, nämlich auf genau 50 %.

EDIT2:@OysterD sehe es so.Wenn der erste Gefangene 50 Kisten öffnen kann, weiß der zweite, ob sich seine Nummer in einer dieser Kisten befindet.Wenn dies der Fall ist, kann er weitere 49 öffnen (und dabei die Box/Nummern-Kombination der 100 Boxen lernen) und schließlich seine Box öffnen.Wenn also der erste Gefangene Erfolg hat, dann haben auch alle Erfolg.Denken Sie daran, dass jeder Gefangene dem anderen eine Möglichkeit bietet, die Kisten/Zahlenkombination für jede Kiste, die er öffnet, genau zu kennen.

Vielleicht lese ich es nicht richtig, aber die Frage scheint schlecht konstruiert zu sein oder es fehlen Informationen.

Wenn er die Nummer findet, die ihm in einer dieser 50 Kisten zugeordnet wurde, kann der Gefangene in einen Raum C gehen und alle Kisten werden erneut geschlossen, bevor der nächste in Raum B aus Raum A geht.Ansonsten werden alle Gefangenen (in den Räumen A, B und C) getötet.

Bedeutet der letzte Satz dort, dass alle Gefangenen getötet werden, wenn ein Gefangener 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 ein Gefangener den Raum B immer in einem identischen Zustand betritt, gibt es keine Möglichkeit für eine Strategie.

Die Gefangenen könnten vor dem Verlassen von Raum A sagen, welches Nummernfach sie öffnen werden.Aber ohne dass nachfolgende Gefangene wissen, ob sie erfolgreich waren oder nicht (vorausgesetzt, ein Misserfolg für einen ist kein Misserfolg für alle), haben sie, wenn der nächste Gefangene Raum B betritt, immer noch die gleichen Chancen, ihre Nummer zu wählen wie der vorherige Gefangene (immer 1:100). .

Wenn ein Versagen eines Einzelnen ein Versagen aller ist, dann könnte jeder nachfolgende Gefangene die Wahrscheinlichkeit, die falsche Kiste zu wählen, um eine Kiste verringern, wenn er weiß, welche Kiste der vorherige Gefangene geöffnet hat, und aufgrund der Tatsache, dass nicht alle getötet wurden.d.h.1:100 für den ersten Gefangenen, 1:99 für den zweiten, bis hin zu 1:1 für den letzten.

Die Gefangenen könnten vereinbaren, dass Gefangener 1 die Kisten 1-50 öffnet.

Wenn alle noch am Leben sind, vereinbaren sie, dass der nächste Gefangene die Kisten 2-51 öffnet.(Die 2 ist willkürlich, aber diese Regel ist einfach zu merken) Seine Überlebenschancen vorausgesetzt, dass P1 überlebt hat sind jetzt 50/99.Sie möchten vermeiden, eine Kiste zu öffnen, wenn Sie wissen, dass der vorherige Mann seine Kiste gefunden hat.

Ich weiß nicht, ob das optimal ist, aber es ist viel besser als zufällig.

Die Überlebenswahrscheinlichkeit sieht so aus

50/100 * 50/99 * 50/98 *. . .50/51 * 1

Ich denke, da keine Kommunikation möglich ist, wäre es die beste Strategie, Folgendes zu tun:

Die Wahrscheinlichkeit jedes Gefangenen so gleichmäßig wie möglich verteilen

Bin ich auf dem richtigen Weg oder nicht?

Für jeden Gefangenen verfügbare Informationen:

Die Anzahl der überlebenden Gefangenen. Wenn Sie also über ein effizientes Kistenauswahlsystem verfügen, das die Reihenfolge verwendet, in der jeder Gefangene Raum B betritt, dann Eine Strategie ist durchaus möglich

Welche Kisten die früheren Gefangenen ausgewählt haben.Natürlich ist keine Kommunikation möglich während der Lauf und es wäre nicht möglich, sich an irgendeine 100er-Box-Picking-Permutation zu erinnern. Sie könnten diese Informationen jedoch zur Berechnung in einem System verwenden Vor der Lauf beginnt.

Meine Meinung:

Zeichnen Sie eine Zahlentabelle mit 2 Spalten. Die erste Spalte enthält die Boxnummer (von Box Nr. 1 bis Box Nr. 100).Jeder Gefangene darf dann 50 Kisten auswählen und welche Kiste er auch immer auswählt, er sollte 1 Markierung in die entsprechende Zeile der zweiten Spalte setzen.

Alle Gefangenen sind jedoch verpflichtet, niemals eine Kiste zweimal auszuwählen.Und kein Kästchen darf mit mehr als 50 markiert sein.Einige Gefangene erhalten möglicherweise weniger Optionen als andere, da einige Kästchen möglicherweise zuerst auf 50 Mark gefüllt werden.

Wenn ein Gefangener in Raum B verlegt wird, öffnet er/sie alle Kästchen, die er/sie markiert hat.

Wenn alle Gefangenen getötet werden, weil jemand ihre Nummer nicht findet, sparen Sie entweder 100 oder 0.Es gibt keine Möglichkeit, 30 Menschen zu retten.

Gleiches Konzept.

Eine weitere Einstellung:

Schreiben Sie eine Liste der ersten 100 Binärzahlen auf, die fünfzig Einsen und fünfzig Nullen enthält.

Sortieren Sie sie vom niedrigsten zum höchsten.

Gefangener Nr. 1 erhält die erste Nummer, Gefangener Nr. 2 die zweite, Gefangener Nr. 3 die dritte und so weiter ...

Jeder Gefangene merkt sich seine/ihre Binärzahl.

Wenn ein Gefangener in Raum B verlegt wird, ordnet er/sie die Binärziffern der Zahl, die er/sie sich gemerkt hat, jedem Kästchen zu. Das höchste Bit wird dem Kästchen ganz links zugeordnet, das nächsthöhere Bit wird dem Kästchen ganz links zugeordnet. ..Das niedrigste Bit wird mit dem Feld ganz rechts abgeglichen.

Er/sie öffnet alle Kisten, die mit 1 übereinstimmen, und lässt geschlossene Kisten zurück, die mit 0 übereinstimmen.

Dies würde die Wahrscheinlichkeit minimieren, da frühe Häftlinge andere Ziffern erhalten als die späteren Häftlinge und Häftlinge, deren Zahlen nahe beieinander liegen, würden Ziffern bekommen, die nahe beieinander liegen.Dies garantiert zwar keine Überlebensfähigkeit, aber wenn die ersten Häftlinge überleben, besteht eine höhere Wahrscheinlichkeit, dass auch die späteren Häftlinge überleben.

Ich habe mir zwar noch keine genauen Zahlen und Gründe ausgedacht, aber das ist eine schnelle Lösung, die mir im Moment einfällt.

In der Frage gibt es keine zeitliche Begrenzung, daher schlage ich vor, dass die Gefangenen sich entscheiden sollten, sich eine Stunde pro Box Zeit zu nehmen und sie in der angegebenen Reihenfolge zu öffnen.Wenn der zweite Gefangene nach 2 Stunden den Raum betreten darf, weiß er, dass der erste Gefangene seine eigene Nummer in Box 2 gefunden hat.Deshalb weiß er, dass er in seiner Sequenz Kasten 2 überspringen muss und die Kästchen 1, 3, 4 ... 51 erste Gefangenen -Chancen für Verlierungen haben 50/100 Geben Sie, dass der erste Gefangene überlebt hat, dann sind die zweiten Gefangenen die Chance, Gewinn zu gewinnen, 50/99, also antworten Sie also antworten scheint zu sein (50 ^51)*49!)/100!Was laut Google 2,89*10^-9 macht, was so gut wie null ist. Auch wenn die Gefangenen die Kästchen wussten, dass die zuvor glücklichen ihre Nummer darin fanden, gäbe es keine Hoffnung

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow