Serie-12

Aufgabe 6

Mike und Bernd haben sich nicht aufs Glatteis führen lassen, d.h. auf den zugefrorenen Teich vor dem Haus schon, aber nicht bei der letzten Aufgabe. Beim Aufwärmen las Bernd in einem Geheimbericht aus Absurdistan. Allerdings stammt der aus dem 18. Jahrhundert und so ist es nicht zu befürchten, dass irgend jemand nächste Woche verlangt einen Untersuchungsauschuss einzurichten.
Der König des Landes wollte aus einer Laune heraus etwas Gutes tun (Das kann nur sehr lange her sein.) In dem Gefängnis des Landes saßen etliche Gefangene und von denen wollte der König einige freilassen. Aber wer sollte es sein? Da kam ihm (???) eine absurde Idee.
Das Gefängnis hatte genau 100 durchnummerierte Zellen, wo bei die erste seit Jahren nur als Abstellkammer diente und nie aufgeschlossen wurde, die spielt also keine Rolle, außer beim Zählen bzw. als Startnummer.
Zu Beginn sind alle Türen zu.
Der Wärter sollte alle Zellen aufschließen - außer Nummer 1 natürlich.
Bei den anderen Rundgängen gilt die Regel: Gehe bis zu einer Tür, die offen ist, schau auf die Zellennummer, diese sei x. Diese Tür bleibt offen. Schließe die Türen 2x, 3x usw. bis zur Nummer 100. Trifft der Wärter dabei auf eine geschlossene Tür, so bleibt diese zu.
Dann beginnt der nächste Rundgang wieder bei Tür 1.
Befehl ist Befehl, sagte sich der Wärter und drehte Runde für Runde. Irgendwann fand er keine Türen mehr, die er schließen musste bzw. durfte, nach der Regel. Es werden alle Gefangen entlassen, die nach beliebig vielen Rundgängen des Wärters in einer offenen Zelle sitzen.
Wie viele Runden muss er mindestens gehen, damit er mit Aufschließen und Zuschließen fertig ist? Wie viele Gefangenen kommen maximal frei, wenn eine Zelle mit je einem Gefangenen belegt ist?
Zu erreichen sind 4 Punkte.

Erster Durchgang: Alle Türen bis auf die Nummer 1 sind offen.
Zweiter Durchgang: Wärter trifft auf die offne Tür 2, die bleibt offen und schließt alle Vielfachen davon.
Dritter Durchgang : Wärter trifft auf die offne Tür 3, die bleibt offen und schließt alle Vielfachen davon, wenn sie geschlossen waren (z.B. 6), dann bleiben sie auch zu.
Vierter Durchgang: Wärter trifft auf die offne Tür 5, die bleibt offen und schließt alle Vielfachen davon, wenn sie geschlossen waren (z.B. 15), dann bleiben sie auch zu.
Fünfter Durchgang: Wärter trifft auf die offne Tür 7, die bleibt offen und schließt alle Vielfachen davon, wenn sie geschlossen waren (z.B. 14), dann bleiben sie auch zu.
Mehr Durchgänge muss er eigentlich nicht mehr machen, denn er träfe nun auf die Tür 11, aber er hat nichts mehr zum Zuschließen, denn alle Vielfachen der 11 (bis zur 100) sind schon zu, diese gilt für alle noch offenen Türen. Es ist leicht zu sehen, dass dies alles Primzahlen sind.
(Die Aufgabe ist also eigentlich nur eine verklausulierte Form des Sieb des Erathotenes.)
Es gibt bis zur 100 genau 25 Primzahlen, also kommen maximal 25 Gefangene frei.