Die 15 Steine des
15er-Spiels
werden zunächst gemischt und in beliebiger Reihenfolge in die 4x4-Kiste
einsortiert. Danach sollen sie durch das verschieben einzelner Steine
zeilenweise in die natürliche Reihenfolge von 1 bis 15 gebracht werden (mit
dem Leerfeld unten rechts). Manchmal kann man diese Aufgabe relativ schnell
lösen, manchmal scheint es unmöglich. Um 1880 war in den USA ein wahres
Spielfieber rund um das 15er-Spiel ausgebrochen. Anders als viele
dachten, hängt die Lösbarkeit des 15er-Spiels aber nicht von der Qualifikation
oder der Tagesform des Spielers ab, sondern von der Ausgangsposition: Bei
genau der Hälfte aller Ausgangspositionen ist die Lösung möglich, bei der
anderen Hälfte nicht.
Die uns interessierende Aufgabe besteht darin, dass durch eine Folge von Zügen
genau zwei Steine (und zwar die 14 und die 15) ihre Plätze tauschen sollen und
alle anderen Steine vorher und nachher an ihrer Startposition stehen sollen.
Hier die Kurzfassung für Mathematiker: Ist die Startkonfiguration eine gerade
Permutation der natürlichen Reihenfolge, so ist die Lösung möglich. Im Falle
einer ungeraden Permutation nicht. Die Unmöglichkeit sieht man folgendermaßen:
Wir denken uns das Leerfeld als einen zusätzlichen Stein. Jede Bewegung eines
normalen Steins ist eine Vertauschung (Transposition) dieses Steins mit dem
Leerfeld. Startet man mit dem Leerfeld unten rechts und endet mit dem Leerfeld
an der selben Stelle, dann hat man insgesamt eine gerade Anzahl von
Transpositionen, d.h. eine grade Permutation ausgeführt. Die geforderte
Vertauschung von 14 und 15 ist aber eine ungerade Permutation.
Es gibt auch eine etwas längere Erklärung, die kein Hintergrundwissen über
Permutationen benötigt. Wir folgen hier der Darstellung in der
Wikipedia: Zu jeder
Anordnung der Steine ermitteln wir eine natürliche Zahl N=N1+N2, von der nur
die Parität wichtig sein wird, d.h. ob sie gerade oder ungerade ist. Ein
beliebiger Zug des 15er-Spiels wird diese Parität nicht ändern, so dass
Anordnungen mit geradem N niemals in eine Anordnung mit ungeradem N überführt
werden können.
Die Bestandteile von N berechnen sich folgendermaßen: N1 (der
Ordnungsparameter) zählt, wieviele Paare von Steinen in der falschen
Reihenfolge stehen: Im Startzustand ist er =0, bei der Aufgabe mit
vertauschten Zahlen 14 und 15 ist er =1, und im schlimmsten Fall, wenn die
Zahlen rückwärts von 15 bis 1 eingeordnet sind, stehen alle Paare falsch
herum, das sind 14*15/2=105. Die Zahl N2 (der Reihenparameter) gibt einfach
nur an, in der wievielten Zeile sich die Leerstelle befindet. Bei der
Endposition ist also N2=4.
Jetzt müssen wir noch zeigen, dass sich bei einem beliebigen Zug die Polarität
von N nicht ändert. Bei waagerechten Zügen ist das ganz klar, da ändern sich
weder N1 noch N2. Ein senkrechter Zug entspricht einer Verschiebung des Steins
um vier Plätz nach vorn oder zurück. Er überspringt sozusagen drei Steine, und
dadurch ändert sich die Reihenfolge für genau drei Paare. Damit ändert sich N1
um 1 oder 3 nach oben oder nach unten, also insgesamt um eine ungerade Zahl.
Zusätzlich ändert sich N2 um 1, so dass die Änderung von N insgesamt
geradzahlig ist (sie kann auch 0 sein). Auf jeden Fall bleibt die Polarität
erhalten.
Wenn man nun durch eine Zugfolge nur die Steine 14 und 15 vertauschen könnte,
müsste sich N von 0 zu 1 ändern, das ist aber wegen der unterschiedlichen
Polarität nicht möglich.
Schlussfolgerung: Manchmal haben wir ein 15er-Spiel vor uns, bei dem
die Steine nicht mit aufeinanderfolgenden Zahlen, sondern mit Teilen eines
Bildes oder Buchstaben versehen sind. Wenn dann zwei Steine identisch sind, so
ist dieses 15er-Spiel jede verlangte Anordnung der anderen Steine lösbar. Es gibt immer eine der
zwei Anordnungen für die zwei identischen Steine, so dass die gewünschte
Polarität vorliegt. Diese Regel "Wir können ja noch die zwei identischen
Steine vertauschen." wird sich als nützlich erweisen.
Frage: Der Beweis oben benutzt, dass es sich bei dem Feld der Größe 4x4
handelt, und zwar an der Stelle, dass bei einem senkrechten Zug genau drei
Steine übersprungen werden und drei ungerade ist. Wie ist die Situation bei
einem verkleinerten Spiel mit einem Spielfeld der Größe 3x3 und acht Steinen:
Lassen sich dann zwei Steine vertauschen?
