Lösung: Vierzehn Fünfzehn
Es ist unmöglich, dieses Puzzle zu lösen. Alle möglichen Konfigurationen der 15 Steine und des leeren Platzes können in zwei Gruppen unterteilt werden. Jede Konfiguration in einer dieser Gruppen ist durch Verschiebungen von jeder anderen Konfiguration in derselben Gruppe erreichbar, jedoch nicht von der anderen Gruppe. Die gewünschte Endkonfiguration (alle Steine in der richtigen Reihenfolge mit dem leeren Platz wieder unten rechts) und die gegebene Startkonfiguration befinden sich nicht in derselben Gruppe. Es ist jedoch möglich, alle Steine in der richtigen Reihenfolge zu platzieren, mit dem leeren Platz oben links (siehe die zweite Frage zum Puzzle)!
Ein Beweis hierfür kann auf der Grundlage der sogenannten Parität jeder Konfiguration erbracht werden: Eine Konfiguration ist gerade oder ungerade. Diese Parität bleibt bei allen erlaubten Zügen erhalten.
Zuerst erklären wir, wie die Parität einer Konfiguration bestimmt wird. Danach werden wir beweisen, dass die Parität bei allen erlaubten Zügen erhalten bleibt.
Die Parität einer Konfiguration wird durch die Summe von N1 und N2 bestimmt. Dabei ist N2 die Nummer der Reihe, in der sich der leere Platz befindet (nummeriert von 1 bis 4). N1 ist die Anzahl der Zahlenpaare, deren Zahlen in der falschen Reihenfolge stehen. N1 wird wie folgt bestimmt:
- Setze alle Zahlen der Steine in eine Reihe (von links nach rechts und von oben nach unten).
- Betrachte alle 105 möglichen Zahlenpaare in dieser Reihe (alle möglichen Kombinationen von zwei Zahlen).
- N1 ist die Anzahl der Zahlenpaare, deren Zahlen in der falschen Reihenfolge stehen.
Ein Beispiel. Angenommen, die aktuelle Konfiguration der Steine sieht wie folgt aus:
| 1 | 2 | 3 | 4 |
| 5 | 6 | 9 | 7 |
| 11 | 8 | 12 | 10 |
| 13 | 14 | 15 |
Jetzt setzen wir die Zahlen in eine Reihe: 1, 2, 3, 4, 5, 6, 9, 7, 11, 8, 12, 10, 13, 14, 15.
Um zu bestimmen, für welche Zahlenpaare die Zahlen in der falschen Reihenfolge stehen, schauen wir für jede Zahl in der Reihe, welche Zahlen rechts von dieser Zahl kleiner sind. So finden wir, dass für 5 der 105 Zahlenpaare die Zahlen in der falschen Reihenfolge stehen: (9, 7), (9, 8), (11, 8), (11, 10) und (12, 10). Also ist N1 = 5.
Der leere Platz befindet sich in diesem Beispiel in Reihe 4, also ist N2 = 4.
Die Parität der Konfiguration in diesem Beispiel ist daher ungerade, da N1 + N2 = 5 + 4 = 9.
Jetzt werden wir beweisen, dass sich die Parität nicht ändert, wenn man einen erlaubten Zug macht. Es gibt zwei Arten von Zügen: Ein Stein kann horizontal oder vertikal verschoben werden.
Bei einer horizontalen Verschiebung (siehe das Beispiel in der Abbildung unten) bleiben sowohl N1 als auch N2 gleich. Die Reihenfolge der Steine ändert sich nämlich nicht, und der leere Platz bleibt in derselben Reihe. Ein horizontaler Zug hat also keinen Einfluss auf die Parität.
| X | → | ||
Bei einer vertikalen Verschiebung (siehe das Beispiel in der Abbildung unten) gelangt der leere Platz eine Reihe höher oder tiefer. N2 nimmt dadurch um 1 zu oder ab. N1 wird um 1 oder 3 zunehmen oder abnehmen. Wenn die Zahlen in einer Reihe stehen, sind nämlich immer genau drei Zahlen zwischen der alten und der neuen Position des verschobenen Steins eingeschlossen. Es können nur Änderungen in den Zahlenpaaren auftreten, in denen sowohl der verschobene Stein (X) als auch eine der eingeschlossenen Zahlen (a, b und c) vorkommen. Alle anderen Zahlenpaare bleiben unverändert. In dem Beispiel unten, in dem Stein X eine Reihe nach unten verschoben wird, nimmt der Wert von N2 um 1 zu. Der Wert von N1 nimmt für jedes der drei Zahlenpaare (X, a), (X, b) und (X, c) um 1 zu oder ab (siehe die Tabelle unten).
| X | a | ||
| b | c | ↓ | |
| Situation vor der Verschiebung | Beitrag zu N1 vor der Verschiebung | Beitrag zu N1 nach der Verschiebung | Änderung von N1 | ||
|---|---|---|---|---|---|
| X > a | X > b | X > c | |||
| nein | nein | nein | 0 | 3 | +3 |
| ja | nein | nein | 1 | 2 | +1 |
| nein | ja | nein | 1 | 2 | +1 |
| ja | ja | nein | 2 | 1 | -1 |
| nein | nein | ja | 1 | 2 | +1 |
| ja | nein | ja | 2 | 1 | -1 |
| nein | ja | ja | 2 | 1 | -1 |
| ja | ja | ja | 3 | 0 | -3 |
Weil sowohl N1 als auch N2 sich mit einem ungeraden Wert ändern, ändert sich der Wert von N1 + N2 um einen geraden Wert. Dadurch bleibt die Parität von N1 + N2 auch bei einer vertikalen Verschiebung gleich.
Die Parität der gegebenen Startkonfiguration (mit den Zahlen 14 und 15 vertauscht und dem leeren Platz unten rechts) ist ungerade (weil N1 + N2 = 4 + 1 = 5). Die Parität der gewünschten Endkonfiguration (alle Zahlen in der richtigen Reihenfolge und der leere Platz unten rechts) ist gerade (weil N1 + N2 = 4 + 0 = 4). Es ist daher unmöglich, durch das Verschieben der Steine von der gegebenen Startkonfiguration zur gewünschten Endkonfiguration zu gelangen.
Die Parität der Konfiguration, in der alle Zahlen in der richtigen Reihenfolge stehen und der leere Platz sich oben links befindet, ist jedoch ungerade (weil N1 + N2 = 1 + 0 = 1). Diese Konfiguration ist also von der gegebenen Startkonfiguration aus erreichbar.
Zurück zum Rätsel