Tüftel & Rätselecke

(mw) Man behauptet, Informatiker seien die geborenen Tüftler. Also, fühlt Euch herausgefordert. Für diese Ausgabe stelle ich den folgenden Klassiker zur Diskussion. Falls Ihr irgendwelche gemeinen Rätsel, Logeleien oder ähnliches gehortet habt, oder Euch im Studium eine konkrete Frage begegnet, zu der ihr eine Lösung sucht, wäre ich für Zusendungen dankbar.

Des Kaisers Palast: Ein Kaiser hat einen Palast mit 1000 Türen (logischerweise nicht in FFM, da könnte sich selbst ein Kaiserso etwas nicht leisten). Alle Türen sind geschlossen. Aus purer Langweile schickt er seinen Diener los, eine jede Tür zuöffnen, die geschlossen ist und jede zu schließen, die offen ist. Also öffnet der Diener alle Tore. Kaum ist er fertig, hat sich der Kaiser eine neue Bosheit ausgedacht und verlangt, er möge nun jede zweite Tür öffnen, wenn sie geschlossen ist und schließen, wenn sie geöffnet ist. Der Diener macht sich ans Werk und schließt also jede Tür mit gerader Nummer. Anschließend wiederholt der Kaiser seinen Befehl, nur daß nun jede dritte Tür zu öffnen bzw. zuschließen sei. Noch mitgekommen? Jetzt sieht die Situation so aus:

auf, zu, zu, zu, auf, auf (dieses Muster wiederholt sich bis zum Ende)

Natürlich muß der Diener im 4. Durchgang den Zustand jeder vierten Tür verändern, dann den jeder fünften, jeder sechsten,...
Wenn nun der arme Diener 1000 Durchgänge überstanden hat, (im letzten Durchgang wurde nur noch die Tür mit der Nummer 1000 verändert (kleiner Tip, sie wurde geschlossen), welche Türen stehen dann offen? Klar, kurze Programmierung spart noch kürzeres Nachdenken, es gibt aber ein sehr einfaches Kriterium und einen einleuchtenden Grund, warum es gerade diese Zahlen sind.