In den Umkleideräumen eines Schwimmbades stehen 100 Personen. Die erste Person öffnet alle Spinde. Die zweite öffnet jeden zweiten Spind. Die dritte ändert den Zustand jedes dritten Spindes, d.h. der Spinde 3, 6, 9 usw. trifft sie auf einen offenen Spind, so verschließt er diesen, trifft er auf einen verschlossenen Spind, so öffnet sie ihn. Die Frage lautet nun: Welche Spinde sind am Ende, wenn alle 100 Personen die Umkleideräume passiert haben, noch offen?

Wir werden diese Fragestellung, wie auch die zuvor schon behandelten Probleme zunächst im klassischen Programmierstil mit Mathematica lösen.Danach werden wir eine Lösung angeben, die mit "Mathematica-Bordmittlen" erzeugt ist und wesentlich näher "am Problem" ist.

My Image

Die klassische Herangehensweise


Wir betrachten hier ein Problem, daß als "Locker-Problem" in der Informatik bekannt ist. Es geht dabei um folgendes:
In den Umkleiderräumen eines Schwimmbades stehen 100 Studenten. Der erste Student verschließt alle Spinde. Der zweite Student öffnet jeden zweiten Spind. Der dritte Student ändert den Zustand jedes dritten Spindes, d.h. der Spinde 3, 6, 9 usw. trifft er auf einen offenen Spind, so verschließt er diesen, trifft er auf einen verschlossenene Spind, so öffnet er ihn. Die Frage lautet nun: Welche Spinde sind am Ende, wenn alle 100 Studenten die Umkleideräume passiert haben, noch offen?
Wir werden diese Fragestellung, wie auch die zuvor schon behandelten Probleme zunächt im klassichen Programmierstil mit
Mathematica lösen. Die Lösung ist hier kein größeres Problem. Die Lösung läßt sich mit zwei geschachtelten Schleifen einfach ermitteln. Der Einfachheit halber beginnen wir erst mit dem zweiten Studenten und der Ausgangssituation, daß alle Spinde offen sind.
Es bleiben also alle Spinde offen deren Nummern Quadratzahlen sind. Ein durchaus nicht offensichtliches Ergebnis.

Stacks Image 50

Die Mathematica Herangehensweise


Nun soll auch dieses Problem wieder im Mathematica Stil angegangen und gelöst werden. Die Grundidee ist dabei die offenen Spinde als Liste von Zahlen zu repräsentieren. Dabei steht +1 für einen offenen Spind und -1 für einen verschlossenen Spind. DieseWahl der Darstellung ermöglicht es die Invertierung des jeweiligen Spindzustandes durch eine Multiplikation mit -1 zu realisieren. Dies wiederum ermöglicht es die zugrundeliegende Iteration mit Hilfe der Mathematica-eigenen Iterationsfunktionen (hier FoldList) zu implementieren. Betrachten wir die Vorgehensweise etwas genauer, indem wir das Problem Schritt für Schritt lösen. Wir betrachten dabei anzahl Spinde. Zunächst die Spinde, dann die Studenten:
Stacks Image 51
Stacks Image 52
Das Auf- oder Zuschließen des Spindes mit der Nummer i entspricht nun dem "Umdrehen" des Vorzeichens an der i-ten Position in der Liste der offenen Spinde. Der Student Nummer k bewirkt also das Umdrehen des Vorzeichens an den Positionen k, 2k, 3k, .. n*k, solange bis n*k größer wird als die Anzahl der Spinde. Diesen Effekt erreicht man einfach dadurch, das die Liste der offenen Spinde mit einer entsprechend generierten Liste multipliziert wird. Diese Listen sind jedoch einfach zu erzeugen. Hier zum Beispiel die Folge für den dritten Studenten
Stacks Image 53
Der Befehl ReplacePart[...] kann nun also benutzt werden, um eine Folge von Listen derart zu erzeugen, daß die i-te Liste die Aktion des i-ten Studenten abbildet. Dazu definieren wir eine Funktion invertieren wie folgt:
Stacks Image 54
Mit Hilfe dieser Funktion können wir nun mit einem einzigen Befehl die Aktionen der Studenten 1 bis n erzeugen:
Stacks Image 55
Damit kann das Problem elegant mit der Funktion FoldList gelöst werden. Mit Hilfe dieser Funktion wird das Verhalten der Studenten 1, 2, 3, ... anzahl einfach durch Multiplikation der entsprechenden Zeile (invertieren[i]) auf den aktuellen Stand der Spinde erzeugt. Die graphische Darstellung erhält man dann einfach mittels der Funktion ArrayPlot
Stacks Image 56
My Image
Schließlich erhalten wir das folgende Mathematica-Programm:
Stacks Image 58
Für die in der Aufgabenstellung genannten 100 Spinde erhalten wir:
Stacks Image 59

Download

Mathematica Notebook
PDF

RapidWeaver Icon

Made in RapidWeaver