Rätsel der Woche Wie viele Schließfächer stehen offen?

Sie stehen vor 100 Schließfächern - und ein Mann macht die Türen nach einer bestimmten Regel immer wieder auf und zu. Nach 100 Durchgängen ist er fertig - und dann sind Sie dran: Wie viele der Türen sind geöffnet?
Schließfächer (Archivbild): Stehen alle offen? Oder doch nicht?

Schließfächer (Archivbild): Stehen alle offen? Oder doch nicht?

Foto: Oliver Berg/ picture-alliance/ dpa

Die Rätsel der vergangenen Wochen hatten häufig mit Logik zu tun. Da wird es Zeit für eine Herausforderung, in der es endlich wieder um richtige Zahlen geht. Geschickt hat die Aufgabe Ulrich Hornauer aus Berlin. Sie ermöglicht einen kleinen Ausflug in die Zahlentheorie.

Sie erinnern sich hoffentlich noch dunkel an Primzahlen. Jene natürlichen Zahlen größer als 1, die nur durch 1 und sich selbst teilbar sind. Diese sind ein wichtiges Studienobjekt von Zahlentheoretikern - und sie spielen auch im neuen Rätsel eine wichtige Rolle:

Wir stehen vor 100 nebeneinander angeordneten Schließfächern, die sämtlich geschlossen sind. Ein Mann hat einen Schlüsselbund mit allen 100 Schlüsseln und wird genau hundertmal an den Schließfächern vorbeigehen und dabei manche öffnen oder schließen.

Beim ersten Durchgang öffnet er alle Fächer. Beim zweiten Durchgang geht der Mann zu jedem zweiten Fach und wechselt deren Zustand. Das heißt: Ist es geschlossen, wird es geöffnet. Ist es bereits offen, wird es geschlossen. Im konkreten Fall schließt er also die Fächer 2, 4, 6, ... 98 und 100, weil vorher ja alle Türen offen standen.

Beim dritten Durchgang ändert er den Zustand jedes dritten Faches - also 3, 6, 9, ... 96, 99. Geschlossene Türen öffnet er, geöffnete schließt er. Beim vierten Durchgang geht es um jedes vierte Fach, beim fünften um jedes fünfte - und so weiter. Beim letzten, dem 100. Durchgang ändert der Mann schließlich nur den Zustand der Tür Nummer 100.

Die Frage lautet: Wie viele der 100 Fächer stehen nach dem 100. Durchgang offen?

Zu schwer? Hier bekommen Sie einige Tipps zur Aufgabe.

Das Problem hat es in sich - ich hatte selbst zu Beginn einige Schwierigkeiten, es richtig zu verstehen.

Vereinfachen Sie die Aufgabe doch erst einmal: Nehmen Sie zum Beispiel zehn Schließfächer und zehn Durchgänge. Das können Sie schnell auf einem Blatt Papier untersuchen. Wenn Sie alles richtig gemacht haben, müssten am Ende drei Türen offen stehen. Damit ist die Aufgabe für zehn Türen schon mal gelöst.

Schauen Sie dann nach, welche der zehn Türen offen stehen. Erkennen Sie ein Muster oder eine Regel? Das könnte helfen, das Problem der 100 Türen zu knacken.

Immer noch zu schwer? Hier gibt's weitere Hilfe.

Bei der vereinfachten Version mit zehn Schließfächern sind nach zehn Durchgängen drei Türen offen, und zwar die mit den Nummern 1, 4 und 9. Wenn Sie sich diese drei Zahlen genauer anschauen, fällt Ihnen vielleicht auf, dass es Quadratzahlen sind - also Zahlen, die durch die Multiplikation einer natürlichen Zahl mit sich selbst entstehen (2x2=4). Das könnte Zufall sein, vielleicht aber auch nicht.

Grafisch umgesetzt sieht das Öffnen und Schließen der Türen übrigens so aus:

Rot steht für geschlossen, grün für offen. Zeile 0 ganz oben zeigt den Anfangszustand, Zeile 1 das Öffnen aller Fächer im ersten Durchgang, Zeile 2 das Schließen jeder zweiten Tür und so weiter. Nach dem zehnten Durchgang (unterste Zeile) sind die Fächer 1, 4 und 9 offen - also grün.

Noch ein paar Fragen, die Sie bei der Aufgabe weiterbringen könnten: Wann steht eine Tür überhaupt offen? Anders gefragt: Wie oft ändert der Mann den Zustand einer bestimmten Tür?

Hier geht es zur Lösung

Wir wollen die Aufgabe allgemein lösen. Die Frage ist, wie oft der Mann den Zustand einer bestimmten Tür ändert. Solange diese Zahl gerade ist, ist die betroffene Tür nach 100 Durchgängen geschlossen, da die Türen am Anfang alle geschlossen waren. Ist die Zahl aber ungerade, steht die Tür offen.

Wir nummerieren die Türen von links nach rechts durch - also von 1 bis 100. Der Mann kommt in Durchgang eins zu allen Türen, durch 1 sind schließlich alle Zahlen teilbar. In Durchgang zwei kommt er zu all den Türen, deren Nummer durch 2 teilbar ist. In Durchgang 3 sind es alle Türen, deren Nummer durch 3 teilbar ist - und so weiter.

Ganz allgemein bedeutet das: Die Anzahl der Zustandsänderungen einer Tür entspricht genau der Anzahl der Teiler ihrer Nummer. Und deshalb stehen am Ende nur die Türen offen, deren Nummer eine ungerade Anzahl von Teilern hat.

Es gibt eine Funktion, mit der wir die Anzahl der Teiler einer natürlichen Zahl berechnen können - die sogenannte Teileranzahlfunktion . Sie wissen wahrscheinlich, dass man jede natürliche Zahl als Produkt von mindestens zwei Primzahlen schreiben kann (Ausnahme: Die Zahl ist selbst eine Primzahl).

Ganz allgemein lässt sich jede natürliche Zahl n wie folgt darstellen:

n = p1e1 * p2e2 * p3e3 * ... pknk

Die Zahlen von p1 bis pk sind dabei die Primteiler von n und e1, e2, ... ek sind die Exponenten der Primzahlen in der Primzahlzerlegung. Denn eine Primzahl kann auch als mehrfacher Faktor auftauchen, siehe 36 = 2*2*3*3 = 22 * 32 .

Die gesuchte Zahl ist laut Teileranzahlfunktion  das folgende Produkt:

Anzahl der Teiler von n = (e1+1) * (e2+1) * (e3+1) * ... * (ek+1)

Exkurs: Warum diese Formel zutrifft, kann man relativ leicht erklären. Wenn wir alle Teiler des Produkts p1e1 * p2e2 * p3e3 * ... pknk suchen, finden wir beispielsweise beim ersten Faktor p1e1 genau (e1+1) verschiedene Möglichkeiten, nämlich p10, p11, p12, p13, ... p1e1. Diese Überlegung können wir für jeden der k Primfaktoren anstellen - und mit etwas Kombinatorik kommen wir dann zum Ergebnis, dass die Gesamtzahl der Teiler von n genau dem Produkt (e1+1) * (e2+1) * (e3+1) * ... * (ek+1) entspricht.

Wir suchen alle Zahlen zwischen 1 und 100, die eine ungerade Anzahl von Teilern haben. Das Produkt (e1+1) * (e2+1) * (e3+1) * ... * (ek+1) muss dann eine ungerade Zahl ergeben. Das ist genau dann der Fall, wenn alle Exponenten von e1, e2 bis ek gerade sind. Denn ein Produkt aus mehreren Zahlen ist nur dann ungerade, wenn sämtliche Faktoren ungerade Zahlen sind.

Wenn aber alle Exponenten gerade sind, muss es sich bei der Zahl um eine Quadratzahl handeln. Das versteht man am besten am Beispiel 36 = 22 * 32. Wir können statt 22 * 32 auch schreiben:

22 * 32 = (2*3) *(2*3) = (2*3)2

Und das ist definitiv eine Quadratzahl.

Damit ist die Aufgabe gelöst. Von 1 bis 100 gibt es genau zehn Quadratzahlen (1, 4, 9, 16, 25, 36, 49, 64, 81, 100) - und die Türen mit genau diesen Nummern stehen offen.

Das Türproblem ergibt auch ein spannendes Muster, wenn man es in einer Grafik darstellt. Sie visualisiert das Öffnen und Schließen der Türen in 100 Durchgängen. Die oberste, vollkommen rote Zeile zeigt den Anfangszustand. Alle Türen von der Nummer 1 (ganz links) bis zur Nummer 100 (ganz rechts) sind geschlossen - also rot. Nach Durchgang 1 (zweite Reihe von oben) stehen alle Türen offen - sind also grün.

Bei Runde 2 (dritte Zeile von oben) wird der Zustand jeder zweiten Tür geändert - und so weiter. So entsteht schließlich ein Muster - und ganz am Ende sind nur noch die Türen grün, deren Nummern Quadratzahlen sind. Wenn Sie solche Spielereien mögen: Ein solches Bild lässt sich auch relativ leicht mit Excel erzeugen.

Die Wiedergabe wurde unterbrochen.