Die offenen Spinde

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.

offeneSpinde[n_]:=Module[{spinde=Table[True,{n}]},
For[i=2,i≤n,i+=1, (*Alle Studenten, außer dem ersten*)
For[j=i,j<n,j+=i,spinde[[j]]=Not[spinde[[j]]]] ]; (* invertieren des Zustands*)
Print[Flatten[Position[spinde,True]]] (* Ausgabe der Lösung*)
]

offeneSpinde[100]

Es bleiben also alle Spinde deren Nummern Quadratzahlen sind offen. Ein durchaus nicht offensichtliches Ergebnis.

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 Multiplikationm mit -1 zu realisieren. Dies wiederum ermöglicht es die zugrundeliegende Ieration mit Hilfe der Mathematica-eigenen Itgerationsfunktionen (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:

Remove[anzahl, offeneSpinde, invertieren,studenten,daten] (* Aufräumen *)

anzahl=20;

offeneSpinde=Table[1,{20}]

Daneben noch die Studenten:

studenten = Range[anzahl]

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

ReplacePart[offeneSpinde,-1,Table[{i},{i,3,anzahl,3}]]

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:

invertieren[k_]:=ReplacePart[offeneSpinde,-1,Table[{i},{i,k,anzahl,k}]]

Mit Hilfe dieser Funktion können wir nun mit einem einzigen Befehl die Aktionen der Studenten 1 bis n erzeugen:

invertieren /@ studenten

Damit kann das Problem elegant mit der Funktion FoldList gelöst werden. Mit Hilfe dieser Funktion wird das Verhalten Studenten 1, 2, 3, ... anzahl einfach durch Multiplikation der entsprechenden Zeile (invertieren[i]) auf den aktuellen Stand der Spinde erzeugt.

daten=FoldList[Times, -offeneSpinde, invertieren /@ studenten];

Die graphische Darstellung ist nun besonders einfach, jede Zeile repräsentiert hier den Durchgang eines Studenten

ArrayPlot[daten,ColorRules->{-1-> Black, 1-> White}, Mesh-> True]

Die nach Durchgang aller Studenten noch offenen Spinde erhält man dann einfach mit:

Position[Last[daten],1] // Flatten

Zusammenfassend erhalten wir das folgende Mathematica Programm:

spinde[n_]:=Module[{daten, offeneSpinde=Table[1,{n}], studenten=Range[n]},
student[k_]:=ReplacePart[offeneSpinde,-1,Table[{i},{i,k,n,k}]];
daten=FoldList[Times,-offeneSpinde,student /@ studenten];
Print[Position[Last[daten],1]// Flatten];
ArrayPlot[daten, ColorRules->{-1-> Black, 1-> White}, Mesh-> True]
]

Für 100 Spinde erhalten wir

spinde[100]