Kennt jemand die Aufgabe? Und weiß jemand wie man das löst?
Man betrachte das sogenannte 15-Puzzle in der Grundstellung (vgl. Abb. 2). Jede Anordnung der 15 Zahlen im 4x4-Schema mit Lücke an Stelle 16 nennen wir Konstellation. Ein zulässiger Spielzug besteht darin, einen der Spielsteine vertikal oder horizontal zu verschieben. Eine zulässige Konstellation ist eine Konstellation, die aus der Grundstellung durch endlich viele zulässige Spielzüge hervorgeht. Zeigen Sie in dieser Aufgabe, dass die Konstellation
1 2 3 4
5 6 7 8
9 10 11 12
13 15 14
nicht zulässig ist. Machen Sie sich dabei zunächst klar, dass jede Folge von Spielzügen eindeutig durch den Weg der Lücke bestimmt ist. Es ist hilfreich, dabei an die Gruppe S 16 zu denken und die Begriffe Transposition und Signum zu benutzen.
Historisches: Das 15-Puzzle ist unter vielen Namen bekannt. Ursprünglich wurde es in den 1870er Jahren vom amerikanischen Spieleerfinder Sam Loyd erfunden. Er fragte, ob es möglich sei durch endlich viele zulässige Züge, die
14 und die 15 miteinander zu vertauschen und bot dabei ein Preisgeld von 1000 USD für die erste richtige Lösung an. Man bedenke, dass das für die damaligen Verhältnisse eine mehr als lukrative Summe gewesen ist. Das Chaos, was er
damit möglicherweise in der Gesellschaft verursacht hat führte dazu, dass 1879 die Mathematiker W. Johnson und W. Story in einem Fachartikel im American Journal of Mathematics sich dieses Puzzles annahmen.
