Follow along with the video below to see how to install our site as a web app on your home screen.
Anmerkung: This feature may not be available in some browsers.
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.
We use essential cookies to make this site work, and optional cookies to enhance your experience.