[Rätsel] 100 Gefangene

[shoulder]

Ein König hat 100 Gefangene, jeder in seiner eigenen Zelle.

Nun lässt er einen Boten durchgehen, der alle Zellen aufschließt.
Danach lässt er einen weiteren Boten durchgehen, der den Zustand jeder zweiten Tür ändert.
Danach das Selbe mit jeder Dritten, jeder Vierten, ... bis er bei jeder Hundertsten angekommen ist, welches der letzte Durchgang ist.

Wieviele und welche Gefangen können nach dem letzten Durchgang fliehen?

Für die Mathe Genies/Coder ein Leichtes. :tongue:

[El-Mo]

Da der König zwar sehr mächtig, aber trotzdem gerecht ist, hat er nur die wirklich bösen Buben gefangen genommen. Und die werden sich, sobald der erste Bote so dumm gewesen ist, alle Zellen zu öffnen, einen Sch*** darum kümmern, was die anderen Boten noch so vor haben, und sofort die Flucht ergreifen :tongue:

[v6ph1]

Trivial:
10 Gefangene kommen frei, wenn nicht noch mehr vor Ende der Aktion geflohen sind.
Es sind die Gafangenen Nr. 1,4,9,16,25,36,49,64,81 und 100.

Es kommen alle Gefangenen frei, deren Zellennummer eine ungerade Anzahl an Teilern (=<100) hat

Und eine Zahl besitzt nur genau dann eine ungerade Anzahl an Teilern, wenn sie eine Quadratzahl ist.

Und jetzt beweise ich das noch:
Sei a eine Zahl, so ergibt besitzt sie zu jedem Teiler b einen Teiler a/b, der von b verschieden ist.
Es gibt nur einen Fall, bei dem a/b und b zusammenfallen, nämlich genau dann, wenn a/b=b.
Stellt man nun diese Gleichung um, bekommt an a=b^2 heraus, a muss also eine Quadratzahl sein.

q.e.d.

mfg
v6ph1

PS: Hoffe, dass ist ausführlich genug.

[shoulder]

Mein Lösungsprogramm sagt du hast recht. :biggrin:

Hab's mal in den Spoiler gesetzt, falls es noch jemand versuchen möchte. :tongue:

[v6ph1]

Mein Lösungsprogramm sagt du hast recht. :biggrin:
Ich habs ja sogar bewiesen. :biggrin:
Und der Beweis ist Wasserdicht.

Hab's mal in den Spoiler gesetzt, falls es noch jemand versuchen möchte. :tongue:
Danke - nicht dran gedacht, will den anderen ja nicht den Spaß vermiesen.

mfg
v6ph1

[El-Mo]

Du hast natürlich recht, v6ph1, auch wenn der Beweis der Äquivalenz etwas holprig ist. Aber: Trotz all der Liebe, die ich meinen Mitmenschen entgegen bringe, muss ich doch glauben, dass der prozentuale Anteil derer, die Deine Argumentation nachvollziehen können, im einstelligen Bereich bleibt :wink2:

Hier also eine Erklärung für die, die in der Bergpredigt explizit erwähnt werden:


Man stelle sich die Zellentüren als durchnummerierte Schalter vor, die nur die Zustände "an" ("offen") oder "aus" ("Tür geschlossen") annehmen können. Anfangs sind alle Schalter aus. Der erste Bote drückt nun alle Schalter an (alle Zahlen von 1 bis 100 sind durch 1 teilbar). Der zweite Bote drückt dann im Anschluss alle Schalter mit gerader Nummer wieder aus (jede gerade Zahl ist durch 2 teilbar). Beim 3. Boten könnte es kompliziert werden, aber die eigentliche Überlegung geht dahin, zu bestimmen, welche Schalter wie oft gedrückt werden, wenn der 100. Bote seine Arbeit getan hat.
Dabei drückt der n. Bote den Schalter genau dann, wenn dieser eine Nummer hat, die durch n teilbar ist. Weiter ist schlussendlich der Schalter an, wenn er eine gerade Anzahl oft gedrückt wurde, und aus, wenn diese Anzahl ungerade ist. Die Frage ist also, welche Zahlen haben eine ungerade Anzahl von Teilern und bestimmen damit die Schalter (Türen), die zum Schluss an (geöffnet) sind, und damit wären wir bei v6ph1's Beweis: Es sind die Quadratzahlen.