Reisepass wiederbekommen

Halli hallo

100 Reisepässe von 100 Personen wurden beschlagnahmt.

Jeder einzelne darf in die Kammer der beschlagnahmnten Pässe, die in 100 Safes drin sind.

Jeder der im Raum war verlässt diesen durch eine andere Türe, ohne Kontaktaufnahme eines nachfolgenden.

Jeder darf 61 Safes öffnen.

Gesucht ist eine Strategie für alle von Anfang an, die Pässe zu finden.
Bei der Beratung stellte sich heraus, dass es keine gute Strategie ist, zufällig Safes öffnen. Die Chance ist dann 0,61 hoch 100.=3,4118 x 10 hoch minus 20.

Ein weiterer Vorschlag war: Die ersten 50 sollten Safes 1 bis 61 öffnen, die übrigen 50 die Safes 40 bis 100. Hierdurch könnte man die Erfolgschance um Faktor 12146 auf 4,144 x 10 hoch minus 16 erhöhen.

Wie kommt man sicher auf mehr als 50%
oder bekommen alle bei richtigem Vorgehen ihre Pässe?

Gruss
Beat

darf jeder nur einmal in den raum? oder darf man auch mehrmals und seine 61 kästchen in mehreren chargen aufmachen?

Hallo Beat,

Gesucht ist eine Strategie für alle von Anfang an, die Pässe
zu finden.

wer soll welche Pässe finden? Jeder seinen eigenen? Oder jeder irgendeinen? Ich tippe auf ersteres, sonst wäre eine optimale Strategie, die Safes der Reihe nach zu öffnen.

Wieviele Pässe darf eine Person einstecken? Maximal einen? Beliebig viele? Ich tippe wieder auf ersteres, sonst nehmen die ersten beiden jeweils 50 Pässe mit und verteilen sie draußen.

Nun aber eine ernstere Frage: Kann eine Person der nächsten (bzw. allen folgenden) Hinweise hinterlassen, indem sie zum Beispiel den Pass im Tresor umdreht, auf einer bestimmten Seite aufblättert, den Tresor von außen markiert etc.?

Viele Grüße,

Andreas

darf jeder nur einmal in den raum? oder darf man auch mehrmals
und seine 61 kästchen in mehreren chargen aufmachen?

Das änderte nur dann etwas, wenn dies eine Kommunikation mit dem Nachfolger erlaubte. Die wäre z. B. dann gegeben, wenn man geöffnete Safes offen stehen liesse. Dann aber bekäme auch bei nur einem Durchgang jeder (ausser evtl. dem ersten) seinen Pass zurück, da nach dem zweiten Besucher bereits alle Safes geöffnet wären und der zweite und alle folgenden ganz gemütlich alle Schränke durchstöbern könnten.

Gruß

Spoiler oder Scherz
die Aufgabe klingt zwar ernst,aber es gibt mehrere Lücken

1.der erste geht rein und öffnet 1-61
hat Glück oder nicht
2.der zweite öffnet 62-100 und kontrolliert 1-61 weil diese ja nochimmer geöffnet sind,steht ja nix von wieder zumachen^^
macht 99%

ohne die Lücke…
ist die wahrscheinlichkeit im Schnitt immer 61%
sagen wir mal man nimmt immer die 61 ersten
im schlimmsten Fall sind die ersten 39 ohne Reisepass
und die nächsten 61 sicher mit Pass!!

noch eine Scherzlösung wäre dass der erste 1-61 nimmt und in Safe 1-22 verteilt so dass jeder nach ihm alle Pässe durchsehn kann…

wenn man pingelisch sein will würde man sagen

das

100 Reisepässe von 100 Personen = 10000 Reisepässe sind und jeder nur einen safe öffnen müsste…

„ohne Kontaktaufnahme eines nachfolgenden“
aber der Vorgänger darf Kontakt aufnehmen kann also vorsagen…

Hallo

Ich habe das Rätsel von:

http://www.mbauerlh4wug.homepage.t-online.de/KK/Kani…

Häuptling Abendwinds Schliessfachproblem.
Kannibalen und Weissenburger.

Literatur:
Nestroy Johann: Komödien Band 3, Häuptling Abendwind.

Die Lösung kenne ich nicht.

Ich vermute, dass ein Plan hinterlassen wird wo welche Pässe liegen.
Dann findet nur der erste seinen vermutlich nicht.
Aber das kanns auch nicht sein.

Gruss

Hallo derdepp

Der Originaltext lautet so:

Einhundert Weissenburger wurden auf einer Reise nach Gross-Lulu verschlagen. Häuptling Abendwind der Sanfte nahm sie alle gefangen und nahm ihnen ihre Reisepässe weg. Dann erklärte er ihnen das Schliessfachspiel von Gross-Lulu.

Die 100 Reisepässe werden nach dem Zufallsprinzip auf 100 Schliessfächer verteilt. Jeder Weissenburger wird dann einzeln in den Raum mit den Schliessfächern geführt um seinen eigenen Pass zu finden. Dazu darf er 50 Schliessfächer öffnen und nachschauen, welche Pässe darin liegen. Anschliessend verlässt er den Raum durch eine zweite Türe um den anderen keine Informationen liefern zu können. Er darf im Raum nichts verändern, muss ihn also so verlassen, wie er ihn angetroffen hat.

Wenn alle Weissenburger ihre Pässe finden, werden sie freigelassen, andernfalls verspeist. Vor dem Spiel dürften sie sich noch eine Strategie überlegen und sogar aufschreiben.
Die verzweifelten Weissenburger schafften es noch, beim gutherzigen Häuptling die Zahl der zu untersuchenden Schliessfächer auf 61 hochzuhandeln.

Nun ist die Strategie gesucht.

Gruss
Beat

Hallo,

Häuptling Abendwinds Schliessfachproblem.

diese Beschreibung beantwortet zumindest meine Fragen: Die ersten beiden wie erwartet, die dritte dahingehend, dass nichts am Raum verändert werden darf, also keine versteckten Hinweise an den nächsten möglich sind (auch das Hinterlassen des Plans im Raum scheidet so aus).

Man kann sich also wirklich allein auf einen vorher zu vereinbarenden, möglichst cleveren Plan „Wer öffnet was?“ konzentrieren.

Andreas

Hi,

ich habe gerade aufgegeben und mir diesen Zeitschriftenartikel besorgt, der auf der Webseite zitiert war, die Beat als Quelle benannt hatte:

Curtin, Eugene; Warshauer, Max: The Locker Puzzle in The Mathematical Intelligencer, Vol. 28, Number 1, Winter 2006, Springer Verlag, New York, ISSN: 0343-6993

Die dort angegebene Strategie zum Suchen der Reisepässe ist erschreckend einfach und elegant; und selbst die Berechnung der Erfolgswahrscheinlichkeit erschließt sich direkt, sobald man sie vorgeführt bekommt … nur muss man erst einmal darauf kommen. :-/

In unserem Fall mit 61 Tresoröffnungen pro Person ergibt sich mit der richtigen Strategie tatsächlich eine Wahrscheinlichkeit von 50,88 %, dass jede Person ihren eigenen Pass findet.

Mehr verrate ich für den Moment nicht; viel Spaß beim Weiterrätseln all denjenigen, die noch nicht aufgegeben haben.

Andreas

PS: Kleiner Tipp: Nach dem Strategiefestlegungstreffen wissen die 100 Personen noch nicht genau im Voraus, welche Tresore jeder von Ihnen öffnen wird. Trotzdem wählen sie keine Tresore per Zufall aus …

Es gibt keine Lösung!
Hallo!

Nach den hier beschriebenen Bedingungen kann es keine Lösung geben. Die Bedingung ist, dass in dem Raum nichts verändert werden darf. Streng genommen darf derjenige, der seinen Pass findet, diesen nicht mal herausnehmen, denn das wäre ja schon eine Veränderung. Der Nachfolgende hat also keine Information, wo sein Pass liegt. Egal, welche Klappen er öffnet und egal nach welcher Strategie, es kann immer sein, dass er zufällig hinter einer der Klappen liegt, die er nicht öffnet.

Das ist unbestreitbare Tatsache.

Anders wäre es, wenn der Finder das Recht hätte, seinen Pass herauszunehmen oder noch besser, entscheiden zu dürfen, ob er das tut oder nicht. Dann könnte er dem Nachfolgenden damit eine Information geben, und sei es nur 1 Bit und auch nur bedingt, das würde bei richtiger Strategie vermutlich genügen.

Aber das darf er ja nicht.

Oder die Bedingungen sind falsch angegeben.

Ursprünglich war diese Bedingung ja gar nicht angegeben, aber dann wäre die Triviallösung, die Klappen offen zu lassen, was ja keinen Sinn macht.

Also: So wie es angegeben ist, ist das Rätsel nicht lösbar.

Grüße

Andreas

Spoiler
Hi,

Die Bedingung ist, dass in dem Raum nichts verändert
werden darf.

richtig, dass ist auch Voraussetzung in dem genannten Artikel (sinngemäß aus dem Gedächtnis wird das so bekräftigt: Man könnte auch 100 identische Räume mit Tresoren und Pässen aufbauen, so dass jede Person das gleiche sieht und kein Informationsfluss zwischen den Personen möglich ist.)

Egal, welche Klappen er öffnet und egal
nach welcher Strategie, es kann immer sein, dass er zufällig
hinter einer der Klappen liegt, die er nicht öffnet.

Das ist unbestreitbare Tatsache.

Richtig; das widerspricht aber nicht der Erkenntnis, dass verschiedene Strategien verschiedene Erfolgswahrscheinlichkeiten haben können, oder? (Und eine davon sogar mehr als 50%; zugegeben, dabei hat sich meine Intuition auch gesträubt, bevor ich den Artikel gelesen hatte.)

Der „Trick“ liegt darin, die Strategie so zu wählen, dass eine möglichst große Korrelation zwischen den Wahrscheinlichkeiten der einzelnen Personen besteht, ihren Pass zu finden. (Also falls eine Person ihren Pass findet, ist es für eine Teilmenge der Personen sehr sehr wahrscheinlich, dass sie ihren Pass auch finden.)

Ich werde mal die Strategie in einem Spoiler-Beitrag verraten.

Viele Grüße,

Andreas

Spoiler: Die Strategie

Die dort angegebene Strategie zum Suchen der Reisepässe ist
erschreckend einfach und elegant;

Die Personen werden durchnummeriert; es gibt also die Personen 1 bis 100, die zugehörigen Pässe 1 bis 100 und einhundert Tresore, die man auch in einer vereinbarten Reihenfolge mit den Zahlen 1 bis 100 bezeichnen kann.

Die Strategie: Jede Person i öffnet zuerst den Tresor i und schaut sich den darin befindlichen Pass mit der Nummer k an: Im Falle k = i ist der eigene Pass gefunden, ansonsten wird als nächstes der Tresor k geöffnet. Das geht solange, bis der Pass gefunden oder die 61 Versuche aufgebraucht sind.

Jeder Pass wird also als Hinweis oder Zeiger auf den nächsten zu öffnenden Tresor benutzt. Das heißt, es bilden sich Ketten von Tresoren und im Falle, dass eine Person ihren Pass findet, sogar zyklische Ketten. (Z.B. schaut Person 1 in Tresor 1, findet dort Pass 3, in Tresor 3 den Pass 7, in Tresor 7 den Pass 1 (ihren eigenen). Diese Strategie hat nun die schöne Eigenschaft, dass alle Personen mit Nummern in diesem Zyklus ihren Pass auch finden werden, weil sie alle die gleichen Ketten verfolgen: Zum Beispiel schaut Person 7 in die Tresore 7, 1 und 3.

Gruß,

Andreas

1 Like

Hallo

Jetzt dämmerts mir langsam. Ich glaub ich komm der Sache näher.

Wenn hundert Pässe in 100 Schliesfächern liegen, dann ist in jedem Schliessfach 1 Pass drin.

Jeder Bürger hat eine ihm zugeteilte Nummer.

Jeder muss mit zB Schliessfach links vorne beginnen zu zählen. Wenn die Schliessfächer nummeriert sind ist es einfacher.
Der erste wird losgeschickt und der zweite weiss, dass er Schliessfach Nr 1 nicht berühren darf. Somit wird kein Fach zweimal geöffnet, das keinen Pass mehr enthält.
Die letzten 60 Leute werden ihren Pass zu 100% finden. Vielleicht noch mehr, wenn man sich alle Fälle durchdenkt.
Aber wenn der erste seinen nicht findet, werden alle Weissenburger aufgegessen.

Ich schätze mal 93 Leute werden ihren Pass haben.

Gruss

Nachtrag
Die Pässe nicht haben, sondern sagen können, in welchem Schliessfach er ist.

Ja, so geht es!
Hallo Andreas!

Nun bin ich aber verblüfft! Ja, so funtioniert es! Tolles Rätsel!

Grüße

Andreas

Ich verstehe nur Bahnhof.
Hallo,

bei einer gesamten Wahrscheinlichkeit von über 50% muss die Einzelwahrscheinlichkeit deutlich über 99% liegen.
Der Erste Teilnehmer muss seinen Pass mit 61 Versuchen also „ziemlich sicher“ finden.
Ich verstehe nicht, wie die Erfolgsw’keit beispielsweise des ersten Teilnehmers überhaupt grösser als 61% sein kann.
Um es in den von dir erwähnten Ketten auszudrücken:
Es ist nicht gerade unwahrscheinlich, dass der erste Teilnehmer „seine“ Kette durchläuft und sein Pass entweder nicht dabei ist, oder die Kette zu lang ist und er ungünstig gestartet ist.

Hilf mir mal vom Schlauch runter…

Gruss,
TR

setzt aber eine zyklischer Verteilung vorraus und keine zufällige!!

Sorry
aber es gibt doch mindestens 61% Treffer!!
alle öffnen 1-61 und 61 treffen auf jedenfall
39 auf jedenfall nicht…
Das Problem was ich sehe ist der erste der seine 61 verballern muss

wenn die Leute rein und wieder rausgehn dürfen wie se wollen ist das ganze einfacher aber dennoch unmöglich

dann würden alle reingehn nacheinander
alle zur 1 bis der richtige drinnen ist

also 1-100 gehn rein und finden in der 1 den Pass der 100.findet es
1-99 gucken die 2 99 findet
1-98 gucken die 3 98 findet
1-97…

findet der 14. in der 10 macht der 15. in der 11 weiter

es ist theoretisch möglich das nur 61% erreicht werden
aber es ist währscheinlicher deutlich mehr zu treffen