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?
