Ein kleines Rätsel

[schindluder]

ich bin zwar muede aber folgender ansatz:

der 1. macht die erste kiste auf

-> ist es sein zettel kann er gehen

-> wenn nicht legt er zurueck und der naechste darf solange bis die erste kiste geknackt ist, ab dann gehts mit der 2. kiste weiter

-> ist die reihe durch darf der allererste wieder ran

das ganze wird so lange wiederholt bis alle mit allen versuchen durch sind oder aber die kisten leer und die zettel zugeordnet


wie rechnet man sowas?

statistisch gesehen braucht man 50,5 versuche fuer kiste nr1
50 versuche fuer kiste nr2
49,5 versuche fuer kiste nr3
49 versuche fuer kiste nr4
48,5 versuche fuer kiste nr5

.
.
.
2 versuche fuer kiste nr99
1,5 versuche fuer kiste nr 100

usw


umgekehrt verlieren die knastbrueder auch versuche mit jedem, der seinen zettel findet und zwar nach folgendem schema

49 versuche fuer kiste nr 1
49 versuche fuer kiste nr 2
48 versuche fuer kiste nr 3
48 versuche fuer kiste nr 4

usw also im endeffekt 2420 versuche


die knastis habe einen gemeinsamen pool von 50 x 100 versuchen = 5000

der einfachheit halber sage ich sie habe im schnitt genau die 2600 versuche, die man zur loesung des problems braucht.

die chance, um damit durchzukommen liegt also ziemlich genau bei 50:50 (anzahl der benoetigten durchschnittlichen versuche gleich der anzahl der durchschnittlich zur verfuegung stehenden versuche)

nach einer woche ist die chance also:

(0,5+ 0,5x0,5 + 0,25x0,5 usw)x 100 %


die wahrscheinlichkeit, dass die knastis nach einer woche wieder draussen sind liegt so bei ueber 99%...


koennte jemand die waerter von der gehaltsliste streichen wegen inkompetenz?

 

[mfb]

@Bauernfänger: Ein Konzept, dass ihnen eine Chance irgendwo in der Gegend gibt. Sie ist nicht genau 1/7, aber zumindest ist bei der erreichbaren Chance eine Woche sehr realistisch (es sind also nicht 0,01%)

@pTReborN: Mit dem Ansatz kann man die Chance zwar verbessern, aber noch lange nicht so weit, dass man nach einer Woche gehen kann.

@schindluder: Die Häftlinge haben keinen gemeinsamen Pool von 5000 Möglichkeiten, und es werden auch keine Kisten entfernt.

 

[schindluder]

das mit dem kisten stimmt, asche auf mein haupt.

was die gemeinsamen moeglichkeiten angeht ist das natuerlich eine vereinfachung aber wenn du dir anguckst was ich gerechnet habe wuesstest du dass ich es rechnerischberuecksichtigt habe, dass es formell kein gemeinsamer pool ist

 

[schindluder]

naechste moeglichkeit die evtl gehen muesste (auch wenns sicher nicht die gsuchte ist)

k
es gibt 2 gruppen an knastis, nach alphabet geordnet. der erste guckt sich sich die ersten 50 kisten an. ich nehme mal der einfachheit halber an er gehoert zu den ersten 50 knastis.

er dreht von den ersten 50 knastis die kisten um, die in die gruppe der ersten 50 knastis gehoeren. (umdrehen ist nicht die reihenfolge manipulieren)

nr 2 kommt es ist unerheblich zu welcher gruppe er gehoert.
er nimmt die anderen 50 kisten und dreht alle davon um, die zur zur gruppe der ersten 50 knastis gehoeren.

die wahrscheinlichkeit das seine kiste dabei ist liegt bei 50 %

die wahrscheinlichkeit, dass beide knastis in die freiheit kommen liegt bei 25%


jeder nachfolgende knasti muss nur wissen ob er in die gruppe der ersten 50 knastis gehoert oder eben nicht und kann dann gezielt alle kisten oeffnen, die fuer ihn in frage kommen. das sind 50 kisten und 50 kisten darf er oeffnen er wird also zwangsweise in freiheit kommen.

also sind alle anderen knastis frei sobald es die ersten beiden geschafft haben. und im schnitt dauert es 4 tage bis alle draussen sind und wie gross die wahrscheinlichkeit ist, dass sie nach spaetestens 7 tage draussen sind ist mir zu muessig zu rechnen

 

[mfb]

Während des Spiels haben die Häftlinge keine Möglichkeit, irgendwie zu kommunizieren. Sie können nicht mit den anderen reden, sie sehen die anderen nicht, sie dürfen die Kisten oder Zettel nicht rumschieben, sie dürfen die Zettel nicht bewegen (auch wenn sie ihren Namen gefunden haben, bleibt ihr Zettel in der Kiste) usw.

Umdrehen habe ich nicht explizit verboten, aber vom Sinn her sollte eigentlich klar sein, dass auch Umdrehen nicht erlaubt ist.

Wäre Umdrehen erlaubt:
H1 (Häftling 1) findet mit 49 Versuchen n Kisten von Gruppe 1 und seinen eigenen Namen (50% Chance. Findet er ihn nicht, ist der Rest unerheblich)
H2 schaut sich zunächst diese n Kisten an und danach noch (50-n) weitere an, von denen sind m aus Gruppe 1. (1+n/50-50/(100-n) Chance, seinen Namen zu finden).
H3 schaut sich n+m an und danach noch (50-n-m) weitere, von denen sind k aus Gruppe 1 (Chance wie bei H2, nur statt n immer n+m)

Statt einer ausführlichen Verteilung nehme ich mal immer den Erwartungswert, also n=25, m=(50-n)(50-n)/(100-n)=25*25/75=8,33, k=(50-25-8,33)^2/(100-(50-25-8,33)) usw.

Ab Häftling 51 finden dann natürlich alle ihren Namen, da die 50 Kisten von Gruppe 1 umgedreht wurden (haben ja alle ihren Namen gefunden)

Multipliziere ich dann die sich ergebenden Chancen auf, erhalte ich 30,3%. Real wird der Wert irgendwo in der Nähe liegen, also schon ganz gut.
Aber eben mit Umdrehen, was verboten ist



Als Tipp zur Lösung: [color=2B2B2B]Ich hatte erst eine unvollständige Aufgabenstellung gesehen. In ihr hat sinngemäß folgender Teil gefehlt:

Er öffnet eine und schaut sich den Zettel darin an. Ist der Name seiner, ist er fertig und wird zurück in seine Zelle gebracht. Ist es nicht sein Name, darf er eine weitere Kiste öffnen und so weiter

Ohne diesen Teil kommt man leicht zur Annahme, man müsste "sofort" entscheiden, welche 50 Kisten man öffnet. Das ist NICHT richtig! Mit diesem Gedanken ist die Aufgabe nicht lösbar.[/color]

 

[ThomasBX]

hihi

Idee habe und denken gehe


Edit:
Also ich habe ein Prinzip gefunden, was ganz gut aussieht, wie wahrscheinlich man damit durchkommt weiss ich aber nicht.

Um das Prinzip zu veranschaulichengehe ich mal von 4 Häftlingen und nur 2 Versuchen aus. Das Prinzip lässt sich dann weiterspinnen. Mit 4 Leuten ist es aber nicht so kompliziert zu beschreiben.

Da es auf der Insel seeehr langweilig ist tauschen sie sich natürlich untereinander aus und kennen ihre Namen. Die Häftlinge waren allesamt unerwünschte Kinder, also dachten sich ihre Eltern wir geben ihnen mal richtig bescheuerte Namen. Sie heissen A, B, C und D. Die Kisten haben die Namen (von links nach rechts) a, b, c und d.

Wie es der Zufall will (oBdA) betritt A als erster der Raum. Er zieht zuerst aus der Kiste a. Leider erwischt er nicht seinen Namen sondern die Karte von C (ObdA). Dann öffnet er die Kiste c. Ist nicht sein Name drin hat er Pech und das Spiel geht am nächsten Tag von neuem los. Ist sein Name in Kiste C legt er den Zettel aus Kiste a in Kiste C und den Zettel aus c mit seinem namen drauf in Kiste a.
Nun kommt B an die Reihe. B weiss nur wenn A Erfolg hatte kommen wir frei. Also nimme B an, das in Kiste a A's Name liegt. Falls A vorher seinen Namen gezogen hat, hätte er ihn in Kiste b gelegt. Also schaut er da mal zuerst nach. Wenn er vrichtiug zieht haben sie gewonnen, weil für die anderen 2 nur noch 2 Kisten da stehen. Zieht er falsch öffnet er Kiste d, denn D stand ja in dem Zettel aus Kiste b. Und Jubel und Freude er findet seinen Zettel, tut diesen in Kiste b.

Für C und D ist das ganze trivial. Sie schauen natürlich in die Kisten c bzw. d zuerst und finden ihre Zettel.

Falls A in Kiste a seinen Namen findet, betritt B den Raum zieht zuerst aus Kiste b öffnet die Kiste dessen Namen drauf steht und hofft das er B findet. Ist dem nicht so geht es von neuem los, findet er seinen Namen kann er die Menge hinreichend vorsortieren.

Dieses Prinzip muss man jetzt nur noch erweitern. Ob man damit die eine Woche knackt weiss ich nicht, aber Zielführend ist es auf jedem Fall. Und zwar besser als 10^-31

ätschibätsch ein angehender Pädagoge hats gelöst, von wegen Mathematiker

 

[destrution]

du hast garnix, zumindest wenn ich jetzt nix falsch verstanden habe

die Kisten werden wieder "originalverpackt"

tja, wenn die kisten alle wieder originalverpackt werden wird das nix mit Zettel und kisten vertauschen

 

[ThomasBX]

Mist du hast recht.
Dabei habe ich vor dem posten nochmal die Aufgabenstellung durchgelesen

 

[mfb]

Du bist aber schon ziemlich nah dran. Nur vertauscht werden dürfen die Zettel nicht.

 

[ThomasBX]

Ziiiiieeemlich nah dran.

Aber etwas denken muss ich noch

Ich glaube sie brauchen x Tage mit
2^x = 100 oder?

oder doch nicht? Ich versuche jetzt mal zuerst zu denken und dann zu reden...

 

[mfb]

Wie viele Tage sie genau brauchen, ist natürlich Zufall und hängt von der Verteilung der Zettel auf die Kiste ab (+ von der Strategie natürlich). Sinnvoll ist nur die Angabe einer Chance, an einem Tag frei zu kommen.

Und Zweierpotenzen sind eigentlich nicht beteiligt.
Auch 10000 Gefangene kämen in ähnlicher Zeit frei, vorausgesetzt die bis zu 50 Millionen Kistenöffnungen gehen in der gleichen Zeit


Edit: ThomasBX hat die Lösung gefunden.

 

[ThomasBX]

Aber ich habe sie noch nicht verstanden zumindest nur teilweise.
Naja morgen geht das Semester los mit langweiligen Vorlesungen und dann habe ich noch ein bisschen was zum knobeln.

 

[f4t3l3s5]

n abend,

wenn ich davon ausgehe, dass mann 1 kiste 1-50 aufmacht, muessen die anderen gefangenen annehmen, dass er darunter seinen namen gefunden hat, das das spiel sonst vorbei waer.
also bleibt fuer de gefangenen 2 einen kiste weniger von den 1-50, die er zu oeffnen hat, da da ja schon der name des1. drin war.

der einfachheit halber kann man dann von der ersten kiste ausgehen.

wenn der 2. jetzt kiste 1 aufmacht soeht er, dass nich seiner sondern der name des vorgaengers draufsteht.

dann kan er getrost weitersuchen, bis er seinen findet, so verschiebt sich das intervall, in dem man suchen muss immer mehr, und man findet seinen zettel.

so oder so aehnlich wuerd ich das loesen, aknn aber auch ganz daneben sein.

um die chancen jetzt genau auszurechnen bin ich zu kaputt. n8

mfg

 

[mfb]

Man kann nur von Kiste 1 ausgehen, wenn man dann nicht mehr zwischen den ersten 50 unterscheidet - sonst könnte der 2. Häftling ja gezielt den Namen seines Vorgängers finden (=Unsinn).
Aber egal wie genau man deinen Ansatz verfolgt, die Chancen wären verschwindend klein (unter 0,000001% ohne nachzurechnen).

 

[Zyrkhan]

Ich hatte heute auf dem Weg zur Schule eine Idee wie man das ganze angehen könnte, ich hoff nur das die Lösung von ThomasBX nicht die ist, die auf Seite 2 steht.

Den Häftlingen werden feste Kistengruppen zugeteilt z.B.
Häftling 1 öffnet die Kisten 1 -10
Häftling 2 die Kisten 5 - 15 usw.
Jeder Häftling merkt sich die Namen die in den Kisten waren und am nächsten Vormittag tragen sie die Namen in eine Tabelle ein.
Das ganze wiederholen sie ein paar Tage, wobei sie weiterhin die Daten eintragen.
Zum schluß rechnen sie für jeden Namen die prozentuale Chance aus, das dieser in einer der Kistengruppe wäre und Listen sie nach der höchsten Erfolgschance auf, z.B. Häftling 1 Kistengruppe 1 30% Kistengruppe 2 10 % usw.

Jeder Häftling öffnet dann die fünf Kistengruppen mit der prozentual höchsten Chance das sein Name darin ist.

Das wäre mein Denkansatz gewesen, der zwar keine 100% Chance für ein rauskommen gibt, aber sie wenigstens ein wenig hebt.

lg,
Zyr

 

[mfb]

Die Wärter mischen die Zettel sehr gut durch, eine solche Statistik hilft nicht weiter (selbst wenn man Jahre damit verbringen würde).
Außerdem müssten die Wärter schon arg schlecht mischen, damit da eine realistische Chance rauskäme.


100% sind eh nicht erreichbar. Aber eben deutlich mehr als 1%.

 

[f4t3l3s5]

ok, bin grad aus der uni heimgekommen und hab mich nochmal dran gesetzt.

ich kam auf ne loesung:

jraa vpu qvr trsnatrara mhsnryyvt ahzzrever, haq qnaa vzzre qvr xvfgr mvrur, iba qre qvr ahzzre qre ahzzre qrf anzraf qrf trsnatra va qre ibeurevtra xvfgr ragfcevpug, zhrffg rf qbpu trura? jne qnf irefgrnaqyvpu?^^

fb ohraqry vpu wrqrasnyyf qvr punapra.
(rot13, editiert von mfb (siehe Post weiter unten))

wenn der ansatz stimmt, wuerd ich das acubh mal ausrechnen, wenns falsch ist, lass ichs gleich;P

 

[ThomasBX]

Ich weiss nicht, ob ich dich richtig verstanden habe, aber wenn ich dich richtig verstanden habe, hört es sich gut an.

Aber leider klapt es nicht immer. Ich habe einfach ein paar Fälle simuliert und dann war recht schnell ersichtlich wo das Problem liegt.
Mittlerweile habe ich auch einigermaßen verstanden warum es funktioniert. Nur habe ich immer noch keinen Ansatz gefunden um auszurechnen, wie wahrscheinlich es ist, dass sie frei kommen.

 

[f4t3l3s5]

n abend,

bin mir nich sicher, aber hab das durchgerechnet, kann das aber nich schreiben, zu bloed bin um einzutippen...., haq xnz nhs ar jnuefpurvayvpuxrvg iba tebrßre nyf rvaf zvahf ybt2 haq qnf vf hrore ahyy xbzzn qerv nyf hrore qervßvt cebmrag
(rot13, editiert von mfb (siehe Post unter diesem))

mfg

 

[mfb]

@lordhaenchenbei: Ist richtig (Lösung+Wahrscheinlichkeit), wobei du die richtige Anfangskiste vergessen hast.
Ich habe mal rot13 über die relevanten Stellen laufen lassen - nicht jeder mag sich unabsichtlich den Rätselspaß verderben lassen