MastersForum

Quoted

Original von plexiq
Meh, stopped being interesting w/ the 30% hint :/

glaub ich nicht

Quoted

Original von plexiq
Welche Art von "indirektem" Informationsfluss wird denn verwendet?

Die "Struktur" des Problems wird ausgenutzt.

Quoted

Original von plexiq
Wenn die 100 Häftlinge schon zu Beginn ihre jeweils 50 zu öffnenden Boxen festlegen, is es imo völlig unmöglich auf >30% zu kommen. Falls wirklich überhaupt kein Informationsfluss während dem Spiel erlaubt ist, muss man die zu öffnenden Boxen komplett im vornherein definieren können, ohne die Gewinnwahrscheinlichkeit zu verändern. Ist doch soweit korrekt Worf?

korrekt, aber deine Schlußfolgerung nicht, dass es dann unmöglich wäre >30% hinzubekommen.

Quoted

Original von plexiq
[Falls die zu öffnenden Boxen dynamisch geändert werden bringt das nur was wenn irgendwelchen neuen Informationen verwendet werden. ie, wider der Rätselaufgabe.]

Bis jetzt wurde gänzlich außer acht gelassen, dass die Zahlen in den Boxen gleichverteilt sind. Natürlich hängt das Ergebnis einer jeden Strategie auch von der konkreten Realisierung des Zufallsexperiments ab, also wie die Zahlen genau auf die Boxen verteilt sind. je nachdem gewinnt man, oder eben nicht, immer mit einer geeigneten Strategie. Diese machen sich die Häftlinge natürlich vorher aus, also bevor sie die konkrete Realisierung der Permutation durch das öffnen der Boxem erfahren. Sie müssen dann "Glück" mit einer für sie günstigen Art der Permutation haben... allerdings geschiet dies eben in >30% aller Fälle!

Da stecken jetzt eigentlich schon viele Tipps drin, ich kann ja noch den kryptischen Tipp hinzufügen, dass die Lösungsidee etwas mit dem Sündenfall und der Strafe Gottes dafür zu tun hat, welche aber nicht alle Menschen betrifft. Zumindest Mathematiker könnten mit etwas um-die-Ecke-denken aus diesem Tipp auf die Lösung kommen.

Quoted

Original von plexiq
Ich glaub das "gleichverteilt" haben alle interpretiert als ein etwas eigenartig formuliertes: Die Zahlen 1-100 wurden zufällig auf Boxen 1-100 verteilt. (ie, jede Zahl genau 1 mal, wobei die Wahrscheinlichkeit dass Zahl x in Box y landet genau 1/100 ist.)

Ja so ist es.

Quoted

Original von plexiq
Was wirklich gemeint war ist, dass in jeder Box eine zufällige Zahl von 1-100 ist, wobei jede der Zahlen unabhänig von einander, gleichverteilt, gezogen wurde?

So natürlich nicht, weil keine Zahl doppelt vorkommen darf, d.h. jede der 100 Häftlingsnummern befindet sich genau einmal in einer der 100 Boxen.

Es ist sozusagen gemeint, dass man unter allen möglichen Permutationen von 100 gleichverteilt eine auswählt. Das ist aber obige Formulierung.

Quoted

Original von pitt82
Wie soll das gehen? Die ersten zwei der 100 Häftlinge haben doch noch nichmal 'ne Chance von >0,3 beide ihren Namen zu ziehen. Da müsste irgendwann einer mit ner Wahrscheinlichkeit > 1 seinen Namen ziehen können.

Zwei Häftlinge zusammen hätten nur dann eine Chance von <30%, wenn sie unabhängig ode nur schwach gekoppelt ziehen. Aber wenn sie unabhängig ziehen, dann kommt man insgesamt auf 2^-100, d.h. dies kann natürlich nicht die Lösung sein. Die Strategie muss deswegen leisten, dass sie es eben schafft besser als unabhängig zu werden.

Genau

Ein recht anschaulicher Artikel auf deutsch:
www.wissenschaft-online.de/artikel/848274

Auch eine recht anschauliche und einfache Erklärung, auf englisch: The condemned prisoners and the boxes

Das Problem in einem Mathematik-Journal betrachtet: The Locker Puzzle

Die optimale Strategie (sie ist optimal, siehe 3. Link) lautet so:
Jeder Häftling öffnet die Box, welche seiner Häftlingsnummer entspricht. Darin findet er eine Zahl, anschließend öffnet er die Box mit eben dieser Zahl darauf uswusf., bis er entweder seine eigene Häftlingsnummer findet oder 50 Boxen geöffnet hat.

Man kann jede Permutation als Kombination ihrer Zyklen (daher der Tipp ) darstellen, siehe Wikipedia Permutation.

Beispiel in Matrixdarstellung:
12345
24513

Um dies in Zyklendarstellung zu transformieren, fängt man bei 1 an.
1 wird auf 2 abgebildet (1 in oberster Zeile suchen und dann die darunterstehende Zahl). jetzt sucht man bei 2, diese wird auf die 4 abgebildet. Jetzt sucht man bei 4, diese wird wieder auf die 1 abgebildet, d.h. man würde von jetzt am im Kreis laufen.
1,2,4 sind schon weg, amchen wir bei 3 weiter, diese wird auf die 5 abgebildet. Jetzt ahben wir alle Zahlen, und probeweise überprüfen wir noch, dass die 5 auch wieder auf die 3 abgebildet wird.
Die Permutation lässt sich also auch schreiben als:
(124)(35)
Damit hat diese Permutation einen zyklus der Länge 3 und einen der Länge 2, es können natürlich auch andere Aufteilungen von Zyklenlängen auftreten.

Da man immer mit seiner eigenen Häftlingsnummer anfängt, befindet man sich auch immer im richtigen Zyklus - die Frage ist nur, ob man seine Nummer auch innerhalb der 50 Versuche erreicht. In unserem Beispiel finden alle Gefangenen ihre Nummer, wenn keiner der Einzelzyklen eine Länge von >50 hat.

Wir berechnen jetzt die Wahrscheinlichkeit dafür, dass der längste Einzelzyklus >50 ist. Da die Zykluslängen in Summe offensichtlich 100 ergeben müssen (siehe Beispiel), kann es auch nur höchstens einen Zyklus der Länge >50 geben.

Jetzt verbleibt noch, mit einfachen kombinatorischen Überlegungen aus der Schule (und eventuell etwas herumprobieren für die Formeln) die Wahrscheinlichkeiten für das Auftreten eines Zyklus der Länge x>50 zu berechnen. Dann summiert man alle Einzelwahrscheinlichkeiten für das Auftreten von Zyklen von 51 bis 100 zusammen und hat damit die Wahrscheinlichkeit, dass die Gefangenen mit dieser Strategie auf jeden Fall verlieren. Folglich muss die Gegenwahrscheinlichkeit die Siegwahrscheinlichkeit sein.

Bei Bedarf kann ich die Rechnung hier auch nochmal hinschreiben, die ist aber in den beiden ersten Artikeln gut erklärt. Die Wahrscheinlichkeit für einen Zyklus der Länge 51 ist 1/51, für einen Zyklus der Länge 52 ist 1/52 usw. Diese Summe wird natürlich von Integral von 1/x majorisiert.

Man kann dieses Problem natürlich auch verallgemeinern, für 2n Häftlinge, welche n mal ziehen dürfen.
Die Niederlagenwahrscheinlichkeit ist dann kleiner als

Für den konkreten Fall mit n=100 Häftlingen ergibt sich, bei genauer Rechnung, eine Erfolgswahrscheinlichkeit von ca. 31,18%.